The multidimensional forest languages O'Neil, Thomas
dc.contributor.department Computer Science 2018-08-23T07:03:32.000 2020-06-30T07:18:14Z 2020-06-30T07:18:14Z Tue Jan 01 00:00:00 UTC 1985 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/
dc.identifier.articleid 13092
dc.identifier.contextkey 6761802
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath rtd/12093
dc.language.iso en
dc.source.bitstream archive/|||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 dissertation Doctor of Philosophy
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
3.98 MB
Adobe Portable Document Format