@article{BordihnHolzerKutrib2011,
  author    = {Bordihn, Henning and Holzer, Markus and Kutrib, Martin},
  title     = {Decidability of operation problems for TOL languages and subclasses},
  series = {Information and computation},
  volume    = {209},
  journal   = {Information and computation},
  number    = {3},
  publisher = {Elsevier},
  address   = {San Diego},
  issn      = {0890-5401},
  doi       = {10.1016/j.ic.2010.11.008},
  pages     = {344 -- 352},
  year      = {2011},
  abstract  = {We investigate the decidability of the operation problem for TOL languages and subclasses. Fix an operation on formal languages. Given languages from the family considered (OL languages, TOL languages, or their propagating variants), is the application of this operation to the given languages still a language that belongs to the same language family? Observe, that all the Lindenmayer language families in question are anti-AFLs, that is, they are not closed under homomorphisms, inverse homomorphisms, intersection with regular languages, union, concatenation, and Kleene closure. Besides these classical operations we also consider intersection and substitution, since the language families under consideration are not closed under these operations, too. We show that for all of the above mentioned language operations, except for the Kleene closure, the corresponding operation problems of OL and TOL languages and their propagating variants are not even semidecidable. The situation changes for unary OL languages. In this case we prove that the operation problems with respect to Kleene star, complementation, and intersection with regular sets are decidable.},
  language  = {en}
}
@article{BordihnKutribMalcher2011,
  author    = {Bordihn, Henning and Kutrib, Martin and Malcher, Andreas},
  title     = {Undecidability and hierarchy results for parallel communicating finite automata},
  series = {International journal of foundations of computer science},
  volume    = {22},
  journal   = {International journal of foundations of computer science},
  number    = {7},
  publisher = {World Scientific},
  address   = {Singapore},
  issn      = {0129-0541},
  doi       = {10.1142/S0129054111008891},
  pages     = {1577 -- 1592},
  year      = {2011},
  abstract  = {Parallel communicating finite automata (PCFAs) are systems of several finite state automata which process a common input string in a parallel way and are able to communicate by sending their states upon request. We consider deterministic and nondeterministic variants and distinguish four working modes. It is known that these systems in the most general mode are as powerful as one-way multi-head finite automata. It is additionally known that the number of heads corresponds to the number of automata in PCFAs in a constructive way. Thus, undecidability results as well as results on the hierarchies induced by the number of heads carry over from multi-head finite automata to PCFAs in the most general mode. Here, we complement these undecidability and hierarchy results also for the remaining working modes. In particular, we show that classical decidability questions are not semi-decidable for any type of PCFAs under consideration. Moreover, it is proven that the number of automata in the system induces infinite hierarchies for deterministic and nondeterministic PCFAs in three working modes.},
  language  = {en}
}