Decidability of structural equivalence of E0L grammars (Q807023)

Two EOL grammars are said to be structurally equivalent if they generate the same sets of teminal syntax trees when one disregards the nonterminals labeling the internal nodes of the trees. The authors prove that the structural equivalence of EOL grammars is decidable, thus solving an open problem posed by T. Ottmann and D. Wood [Structural equivalence of EOL grammars, Research Report CS-89-40, Univ. of Waterloo (1989)]. The proof is based on the use of so-called height-counting tree automata which are finite bottom-up tree automata that remember the heights of the subtrees processed so far.