@article{Bordihn2005,
  author    = {Bordihn, Henning},
  title     = {On the number of components in cooperating distributed grammar systems},
  issn      = {0304-3975},
  year      = {2005},
  abstract  = {It is proved that the number of components in context-free cooperating distributed (CD) grammar systems can be reduced to 3 when they are working in the so-called sf-mode of derivation, which is the cooperation protocol which has been considered first for CD grammar systems. In this derivation mode, a component continues the derivation until and unless there is a nonterminal in the sentential form which cannot be rewritten according to that component. Moreover, it is shown that CD grammar systems in sf-mode with only one component can generate only the context-free languages but they can generate non-context-free languages if two components are used. The sf-mode of derivation is compared with other well-known cooperation protocols with respect to the hierarchies induced by the number of components. (C) 2004 Elsevier B.V. All rights reserved},
  language  = {en}
}
@article{BordihnHolzerKutrib2005,
  author    = {Bordihn, Henning and Holzer, Markus and Kutrib, Martin},
  title     = {Unsolvability levels of operation problems for subclasses of context-free languages},
  issn      = {0129-0541},
  year      = {2005},
  abstract  = {We investigate the operation problem for linear and deterministic context-free languages: Fix an operation on formal languages. Given linear (deterministic, respectively) context-free languages, is the application of this operation to the given languages still a linear (deterministic, respectively) context-free language? Besides the classical operations, for which the linear and deterministic context-free languages are not closed, we also consider the recently introduced root and power operation. We show non-semidecidability, to be more precise, we show completeness for the second level of the arithmetic hierarchy for all of the aforementioned operations, except for the power operation, if the underlying alphabet contains at least two letters. The result for the power opera, tion solves an open problem stated in Theoret. Comput. Sci. 314 (2004) 445-449},
  language  = {en}
}