The multidimensional forest languages

dc.contributor.author O'Neil, Thomas
dc.contributor.department Computer Science
dc.date 2018-08-23T07:03:32.000
dc.date.accessioned 2020-06-30T07:18:14Z
dc.date.available 2020-06-30T07:18:14Z
dc.date.copyright Tue Jan 01 00:00:00 UTC 1985
dc.date.issued 1985
dc.description.abstract <p>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.</p>
dc.format.mimetype application/pdf
dc.identifier archive/lib.dr.iastate.edu/rtd/12093/
dc.identifier.articleid 13092
dc.identifier.contextkey 6761802
dc.identifier.doi https://doi.org/10.31274/rtd-180813-13371
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath rtd/12093
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/65423
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/rtd/12093/r_8524683.pdf|||Fri Jan 14 19:12:24 UTC 2022
dc.subject.disciplines Computer Sciences
dc.subject.keywords Computer science
dc.title The multidimensional forest languages
dc.type article
dc.type.genre dissertation
dspace.entity.type Publication
relation.isOrgUnitOfPublication f7be4eb9-d1d0-4081-859b-b15cee251456
thesis.degree.level dissertation
thesis.degree.name Doctor of Philosophy
File
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
r_8524683.pdf
Size:
3.98 MB
Format:
Adobe Portable Document Format
Description: