Degree Type

Dissertation

Date of Award

1987

Degree Name

Doctor of Philosophy

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.

DOI

https://doi.org/10.31274/rtd-180813-12703

Publisher

Digital Repository @ Iowa State University, http://lib.dr.iastate.edu/

Copyright Owner

Annette Virginia Dittmer Schoenberger

Language

en

Proquest ID

AAI8716816

File Format

application/pdf

File Size

140 pages

Share

COinS