zbMATH — the first resource for mathematics

Tree automata. (English) Zbl 0537.68056
Budapest: Akadémiai Kiadó. 235 p. DM 64.00 (1984).
The mathematical theory of tree automata is a relatively new field in Computer Science, still lacking in widely accepted formalisms. Yet, this monograph has a uniform presentation, the language chosen by the authors being that of universal algebra. Thus, a tree is simply a \(\Sigma\)-term over X, in the usual sense, where \(\Sigma\) (the ”operator domain”) is a finite nonempty set together with an arity mapping and X is a set of ”variables”. The text is divided into four chapters. In the first chapter general notions about universal algebras, lattices, automata and formal languages are presented such that the book is self contained. The topics in chapters 2, 3 and 4, respectively, are: tree (forest) recognizers and generators, operations on trees and decision problems; context-free languages in connection with tree recognizers; tree transducers and tree transformations. Each chapter contains exercises, open problems and bibliographical remarks. Applications of the theory in other fields (mathematical linguistics, decision problems in mathematical logic, pattern recognition) are also considered. We warmly recommend this outstanding book.
Reviewer: C.Masalagiu

68Q45 Formal languages and automata
68T10 Pattern recognition, speech recognition
03B25 Decidability of theories and sets of sentences