OI and IO multidimensional forest languages

Abstract

<p>The OI tree languages are generalized to an OI n-dimensional forest language hierarchy in a manner analogous to the generali- zation of the IO tree languages to the IO n-dimensional forest hierarchy of Baldwin 1 . This involves the generalization of the substitution of trees into trees and sets of trees into sets of trees to include IO and OI n-dimensional forests. The frontier function is extended to include the expansion of nonterminals. The Engelfriet-Schmidt language hierarchy is shown to be contained in the OI n-dimensional hierarchy. The IO n-dimensional forest languages are shown to be the n-dimensional frontiers of the (n + 1)-dimensional OI forest languages. It is established that the OI macro languages are equivalent to the string languages of the OI 3-dimensional forest languages. It is also shown that the OI forest languages are closed under intersection with the regular forest languages and that dead symbols can be removed from the grammars. Finally, an extension of;the n-dimensional languages is presented that allows the definition of grammars for a larger class of languages; 1 Baldwin, W. A. Hypertrees - A Study in Language Specification. Ph.D. thesis. Iowa State University, 1983.</p>