TY  - JOUR
A1  - Bordihn, Henning
A1  - Holzer, Markus
T1  - Programmed grammars and their relation to the LBA problem
JF  - Acta informatica
N2  - 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.
KW  - programmed grammars
KW  - accepting grammars
KW  - LBA problem
KW  - degree of non-regulation
KW  - leftmost derivations
Y1  - 2006
U6  - https://doi.org/10.1007/s00236-006-0017-9
SN  - 0001-5903
VL  - 43
SP  - 223
EP  - 242
PB  - Elsevier
CY  - New York
ER  -