- Treffer 1 von 1
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.
| Verfasserangaben: | Henning BordihnORCiD, Markus HolzerGND |
|---|---|
| DOI: | https://doi.org/10.1007/s00236-006-0017-9 |
| ISSN: | 0001-5903 |
| Titel des übergeordneten Werks (Englisch): | Acta informatica |
| Verlag: | Elsevier |
| Verlagsort: | New York |
| Publikationstyp: | Wissenschaftlicher Artikel |
| Sprache: | Englisch |
| Datum der Erstveröffentlichung: | 04.07.2006 |
| Erscheinungsjahr: | 2006 |
| Datum der Freischaltung: | 03.05.2020 |
| Freies Schlagwort / Tag: | LBA problem; accepting grammars; degree of non-regulation; leftmost derivations; programmed grammars |
| Band: | 43 |
| Seitenanzahl: | 20 |
| Erste Seite: | 223 |
| Letzte Seite: | 242 |
| Organisationseinheiten: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik und Computational Science |
| DDC-Klassifikation: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme |
| Peer Review: | Referiert |
