OI and IO multidimensional forest languages

Thumbnail Image
Schoenberger, Annette
Major Professor
Committee Member
Journal Title
Journal ISSN
Volume Title
Research Projects
Organizational Units
Organizational Unit
Computer Science

Computer Science—the theory, representation, processing, communication and use of information—is fundamentally transforming every aspect of human endeavor. The Department of Computer Science at Iowa State University advances computational and information sciences through; 1. educational and research programs within and beyond the university; 2. active engagement to help define national and international research, and 3. educational agendas, and sustained commitment to graduating leaders for academia, industry and government.

The Computer Science Department was officially established in 1969, with Robert Stewart serving as the founding Department Chair. Faculty were composed of joint appointments with Mathematics, Statistics, and Electrical Engineering. In 1969, the building which now houses the Computer Science department, then simply called the Computer Science building, was completed. Later it was named Atanasoff Hall. Throughout the 1980s to present, the department expanded and developed its teaching and research agendas to cover many areas of computing.

Dates of Existence

Related Units

Journal Issue
Is Version Of

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.

Subject Categories
Thu Jan 01 00:00:00 UTC 1987