Defining families of trees with E0L grammars (Q1179185)

The key observation is that some rewriting systems of context-free type provide a useful and precise way of defining many well-known trees such as 1-2 trees, 2-3 trees, brother trees, etc. Many basic questions arising when the family of EOL grammars is chosen as such a tree-generating mechanism are considered. The height and ultimate height equivalence problems for EOL grammars are shown to be decidable. The structured equivalence problem is solved in some special cases. Moreover, EOL grammars generating exactly the sets of 1-2 and 2-3 trees are characterized.