The multidimensional forest languages

Abstract

<p>A multidimensional forest is a data structure which is a generalization of the conventionally-defined forest. One- and two-dimensional forests correspond to strings and conventional forests respectively. Regular forest grammars can be written to produce sets of n-dimensional forests, and a frontier operation can be applied to sets of n-dimensional forests to yield sets of strings. Thus, n-dimensional regular forest grammars define a class of string languages for each value of n;One-dimensional forest grammars yield exactly the regular languages. Two dimensional forest grammars yield all the context-free languages and perhaps some non-context-free languages which can be produced without copying substrings. Three-dimensional forests grammars yield all the IO macro languages and at least some of the OI macro languages. The frontier operation on three-dimensional forests has the same copying power as the derivation operation in macro grammars, but it has more deleting power. The enhanced deleting power of a three-dimensional forest grammar allows both IO and OI macro derivations to be simulated in a single formal system.</p>