| Article ID: | iaor1992350 |
| Country: | Netherlands |
| Volume: | 32 |
| Issue: | 2 |
| Start Page Number: | 195 |
| End Page Number: | 209 |
| Publication Date: | Jul 1991 |
| Journal: | Discrete Applied Mathematics |
| Authors: | Ottmann Thomas, Wood Derick |
The authors consider E0L grammars as tree-generating mechanisms. This leads to questions of height, weight, and structural equivalence of E0L grammars. Height equivalence is solved completely, weight equivalence remains open, and structural equivalence is solved for two special cases. The authors characterize E0L grammars with two nonterminals that generate exactly the sets of 1-2 and 2-3 trees.