@article{BordihnHolzer2006,
  author    = {Bordihn, Henning and Holzer, Markus},
  title     = {Programmed grammars and their relation to the LBA problem},
  series = {Acta informatica},
  volume    = {43},
  journal   = {Acta informatica},
  publisher = {Elsevier},
  address   = {New York},
  issn      = {0001-5903},
  doi       = {10.1007/s00236-006-0017-9},
  pages     = {223 -- 242},
  year      = {2006},
  abstract  = {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.},
  language  = {en}
}