Multidimensional trees

AbstractA new data structure is presented which may be used to specify programming languages. It is called a multidimensional tree. It is an extension of the normal concept of a tree, which is a two-dimensional concept, into higher dimensions. It is shown that a string may be considered a one-dimensional tree, and a node by itself, a zero-dimensional tree. Forests are defined, analogous to tree forests, except that they may have higher dimensions. A frontier operation is defined which reduces the dimension of its argument by one, enabling strings to be generated from higher dimensional objects. Grammars and automata are defined which allow the definition of languages of multidimensional trees, and therefore string languages. It is shown that this concept is useful in computations—there are useful internal representations. The language hierarchy is related to the language classes of regular, context free, and macro languages