Mappings and grammars on trees

Recent developments in the theory of automata have pointed to an extension of the domain of definition of automata from strings to trees. Here we study certain sets, functions, and relations on trees using natural generalizations of ordinary automata theory. Why pursue such a generalization? First, because enlarging the domain of automata theory may strengthen and simplify the subject in the same way that emphasizing strings rather than natural numbers already has done. Second, because parts of mathematical linguistics can be formalized easily in a tree-automaton setting. The theories of transformational grammars and of syntax-directed compilation are two examples. A two-dimensional automata theory seems better suited to handle concepts arising in these areas than does the conventional theory. The algebraic properties of finite automata on trees have been extensively studied; see Brainerd [5], Doner [8], Mezei and Wright [12], Thatcher [15], Thatcher and Wright [17], and Arbib and Give'on [4]. The notion of recognizable set is central to these papers. A finite checking scheme (automaton) is used on an inp/lt tree. The scheme analyzes a tree from the bottom (leaves) up to the top (root), classifying the tree as acceptable or not. The recognizable set associated with the automaton is the set of all acceptable trees. Here we will define sets of trees produced by finite-state generative schemes. In this respect, making automata work from the top down instead of the bottom up is convenient. Rabin [13] was the first to use this idea; his purpose was to define recognizable sets of infinite trees. We do not consider such trees here; our emphasis is on generation, but the top-down concept is important for all our definitions. We use Thatcher and Wright's algebraic formalism to give succinct descriptions of linguistic constructions in the tree case. Using these constructions, we investigate decision problems and closure properties. Our results should clarify