In the authors’ hierarchy of multidimensional trees, an n -dimensional tree consists of a node (root) followed by an n - 1 -dimensional tree the nodes of which are n -dimensional trees again. The usual trees are of dimension 2, strings are regarded as trees of dimension 1, and single nodes are of dimension 0. An ( n , k )-forest is a k -dimensional tree of ( n , k + 1 )-forests; the usual forests are of type (2,1), that is, they are strings of trees. A generalized frontier operation reduces the dimension by one; repeated application of this operation leads to strings.

This concept is used to define tree grammars and tree automata. The language associated with a grammar of dimension n and rank k is a set of ( n , k )-forests. By applying the frontier operation, this set can be mapped to sets of lower-level forests and eventually to strings. The string languages associated with (1,1)-grammars are regular; (2,2)-grammars lead to context-free languages; and (3,3)-grammars correspond to IO macro grammars. By increasing the dimension, we can define a hierarchy of string languages all members of which are context-sensitive, but not all context-sensitive languages can be found in this hierarchy.

This paper is an extended abstract of Baldwin’s dissertation and addresses specialists in formal language theory. No proofs are given, and only a few examples illustrate the definitions. For all details, the reader is referred to the original work.