R70-10 The Minimalization of Tree Automata

This paper contributes to the literature on tree automata (also known as algebra automata), which is providing new insights at the interface between automata theory and formal language theory—an interface which hopefully will show increasing relevance both to linguists and compiler writers. Formal language theory has long employed pushdown automata, linear bounded automata, etc., to process, parse, and recognize the strings of a formal language. Lurking in the background have been the derivation trees which show how such strings can be derived by various rewriting rules from some initial symbol. The new approach (spurred by the linguists´ interest in transformational grammars which actually transform derivation trees, and by Buchi´s observation—built upon by such workers as Mezei, Thatcher, Eilenberg, Wright, and Giveon in the pages of Information and Control—that ordinary automata may be viewed as a special kind of universal algebra) looks at automata that act directly on the trees, rather than on the strings they produce.