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
1 - 1 of 1
No Thumbnail Available
- Name:
- r_8524683.pdf
- Size:
- 3.98 MB
- Format:
- Adobe Portable Document Format
- Description: