@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}
}
@article{BordihnFernauHolzeretal.2006,
  author    = {Bordihn, Henning and Fernau, Henning and Holzer, Markus and Manca, Vincenzo and Martin-Vide, Carlos},
  title     = {Iterated sequential transducers as language generating devices},
  series = {Theoretical computer science},
  volume    = {369},
  journal   = {Theoretical computer science},
  number    = {1},
  publisher = {Elsevier},
  address   = {Amsterdam},
  issn      = {0304-3975},
  doi       = {10.1016/j.tcs.2006.07.059},
  pages     = {67 -- 81},
  year      = {2006},
  abstract  = {Iterated finite state sequential transducers are considered as language generating devices. The hierarchy induced by the size of the state alphabet is proved to collapse to the fourth level. The corresponding language families are related to the families of languages generated by Lindenmayer systems and Chomsky grammars. Finally, some results on deterministic and extended iterated finite state transducers are established.},
  language  = {en}
}