The multidimensional forest languages
Date
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Journal Issue
Series
Department
Abstract
A multidimensional forest is a data structure which is a generalization of the conventionally-defined forest. One- and two-dimensional forests correspond to strings and conventional forests respectively. Regular forest grammars can be written to produce sets of n-dimensional forests, and a frontier operation can be applied to sets of n-dimensional forests to yield sets of strings. Thus, n-dimensional regular forest grammars define a class of string languages for each value of n;One-dimensional forest grammars yield exactly the regular languages. Two dimensional forest grammars yield all the context-free languages and perhaps some non-context-free languages which can be produced without copying substrings. Three-dimensional forests grammars yield all the IO macro languages and at least some of the OI macro languages. The frontier operation on three-dimensional forests has the same copying power as the derivation operation in macro grammars, but it has more deleting power. The enhanced deleting power of a three-dimensional forest grammar allows both IO and OI macro derivations to be simulated in a single formal system.