Institut für Informatik und Computational Science
Refine
Has Fulltext
- no (1)
Year of publication
- 2006 (1)
Document Type
- Article (1)
Language
- English (1)
Is part of the Bibliography
- yes (1)
Keywords
- leftmost derivations (1) (remove)
Institute
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.