Tree Languages

The theory of tree automata and tree languages emerged in the middle of the 1960s quite naturally from the view of finite automata as unary algebras advocated by J. R. Büchi and J. B. Wright. From this perspective the generalization from strings to trees means simply that any finite algebra of finite type can be regarded as an automaton which as inputs accepts terms over the ranked alphabet formed by the operation symbols of the algebra, and these terms again can be seen as (formal representations of) labeled trees with a left-to-right ordering of the branches. Strings over a finite alphabet can then be regarded as terms over a unary ranked alphabet, and hence finite automata become special tree automata and string languages unary tree languages. The theory of tree automata and tree languages can thus be seen as an outgrowth of Büchi’s and Wright’s program which had as its goal a general theory that would encompass automata, universal algebra, equational logic, and formal languages. Some interesting vistas of this program and its development are opened by Büchi’s posthumous book [Büc89] in which many of the ideas are traced back to people like Thue, Skolem, Post, and even Leibniz.