Programmed grammars and their relation to the LBA problem
- We consider generating and accepting programmed grammars with bounded degree of non-regulation, that is, the maximum number of elements in success or in failure fields of the underlying grammar. In particular, it is shown that this measure can be restricted to two without loss of descriptional capacity, regardless of whether arbitrary derivations or left-most derivations are considered. Moreover, in some cases, precise characterizations of the linear bounded automaton problem in terms of programmed grammars are obtained. Thus, the results presented in this paper shed new light on some longstanding open problem in the theory of computational complexity.
| Author details: | Henning BordihnORCiD, Markus HolzerGND |
|---|---|
| DOI: | https://doi.org/10.1007/s00236-006-0017-9 |
| ISSN: | 0001-5903 |
| Title of parent work (English): | Acta informatica |
| Publisher: | Elsevier |
| Place of publishing: | New York |
| Publication type: | Article |
| Language: | English |
| Date of first publication: | 2006/07/04 |
| Publication year: | 2006 |
| Release date: | 2020/05/03 |
| Tag: | LBA problem; accepting grammars; degree of non-regulation; leftmost derivations; programmed grammars |
| Volume: | 43 |
| Number of pages: | 20 |
| First page: | 223 |
| Last Page: | 242 |
| Organizational units: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik und Computational Science |
| DDC classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme |
| Peer review: | Referiert |
