Decidability of structural equivalence of E0L grammars. (English) Zbl 0729.68039

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.
Reviewer: M.Linna (Naasa)


68Q42 Grammars and rewriting systems
Full Text: DOI


[1] Aho, A., Indexed grammars—An extension of context-free grammars, J. Assoc. Comput. Mach., 15, 647-671 (1968) · Zbl 0175.27801
[2] Gécseg, F.; Steinby, M., Tree Automata (1984), Akadémiai Kiadó: Akadémiai Kiadó Budapest · Zbl 0396.68041
[3] Ginsburg, S.; Harrison, M., Bracketed context-free languages, J. Comput. System Sci., 1, 1-23 (1967) · Zbl 0153.00802
[4] McNaughton, R., Parenthesis grammars, J. Assoc. Comput. Mach., 14, 490-500 (1967) · Zbl 0168.01206
[5] Ottmann, T.; Wood, D., Defining families of trees with E0L grammars, (Research Report CS-89-39 (1989), University of Waterloo) · Zbl 0746.68054
[6] Ottmann, T.; Wood, D., Structural equivalence of E0L grammars, (Research Report CS-89-40 (1989), University of Waterloo) · Zbl 0769.68074
[7] Paull, M.; Unger, S., Structural equivalence of context-free grammars, J. Comput. System Sci., 2, 427-463 (1968) · Zbl 0179.02301
[8] Rozenberg, G.; Salomaa, A., The Mathematical Theory of L Systems (1980), Academic Press: Academic Press New York · Zbl 0365.68072
[9] Salomaa, A., Formal Languages (1973), Academic Press: Academic Press New York · Zbl 0262.68025
[10] Thatcher, J. W., Tree automata: an informal survey, (Aho, A. V., Currents in the Theory of Computing (1973), Prentice Hall: Prentice Hall Englewood Cliffs, NJ), 143-172
[11] Wood, D., Theory of Computation (1987), Wiley: Wiley New York · Zbl 0734.68001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.