OI and IO multidimensional forest languages

Date
1987
Authors
Schoenberger, Annette
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Computer Science
Organizational Unit
Journal Issue
Series
Department
Computer Science
Abstract

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.

Comments
Description
Keywords
Citation
Source