@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}
}
@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}
}
@book{BenschBoldtBordihnetal.2004,
  author    = {Bensch, Suna and Boldt, Oliver and Bordihn, Henning and J{\"u}rgensen, Helmut},
  title     = {Workshop "Formale Methoden der Linguistik" und "14. Theorietag Automaten und Formale Sprachen"},
  series = {Preprint / Universit{\"a}t Potsdam, Institut f{\"u}r Informatik},
  volume    = {2004, 2},
  journal   = {Preprint / Universit{\"a}t Potsdam, Institut f{\"u}r Informatik},
  publisher = {Univ.},
  address   = {Potsdam},
  issn      = {0946-7580},
  pages     = {144 S.},
  year      = {2004},
  language  = {de}
}
@article{Bordihn2004,
  author    = {Bordihn, Henning},
  title     = {Context-freeness of the power of context-free languages is undecidable},
  issn      = {0304-3975},
  year      = {2004},
  abstract  = {The power of a language L is the set of all powers of the words in L. In this paper, the following decision problem is investigated. Given a context-free language L, is the power of L context-free? We show that this problem is decidable for languages over unary alphabets, but it is undecidable whenever languages over alphabets with at least two letters are considered. (C) 2003 Elsevier B.V. All rights reserved},
  language  = {en}
}
@phdthesis{Bordihn2011,
  author    = {Bordihn, Henning},
  title     = {Contributions to the syntactical analysis beyond context-freeness},
  url       = {http://nbn-resolving.de/urn:nbn:de:kobv:517-opus-59719},
  school      = {Universit{\"a}t Potsdam},
  year      = {2011},
  abstract  = {Parsability approaches of several grammar formalisms generating also non-context-free languages are explored. Chomsky grammars, Lindenmayer systems, grammars with controlled derivations, and grammar systems are treated. Formal properties of these mechanisms are investigated, when they are used as language acceptors. Furthermore, cooperating distributed grammar systems are restricted so that efficient deterministic parsing without backtracking becomes possible. For this class of grammar systems, the parsing algorithm is presented and the feature of leftmost derivations is investigated in detail.},
  language  = {en}
}
@misc{BordihnNagyVaszil2018,
  author    = {Bordihn, Henning and Nagy, Benedek and Vaszil, Gy{\"o}rgy},
  title     = {Preface: Non-classical models of automata and applications VIII},
  series = {RAIRO-Theoretical informatics and appli and applications},
  volume    = {52},
  journal   = {RAIRO-Theoretical informatics and appli and applications},
  number    = {2-4},
  publisher = {EDP Sciences},
  address   = {Les Ulis},
  issn      = {0988-3754},
  doi       = {10.1051/ita/2018019},
  pages     = {87 -- 88},
  year      = {2018},
  language  = {en}
}
@article{BordihnBottoniLabellaetal.2017,
  author    = {Bordihn, Henning and Bottoni, Paolo and Labella, Anna and Mitrana, Victor},
  title     = {Networks of picture processors as problem solvers},
  series = {Soft Computing},
  volume    = {21},
  journal   = {Soft Computing},
  publisher = {Springer},
  address   = {New York},
  issn      = {1432-7643},
  doi       = {10.1007/s00500-016-2206-y},
  pages     = {5529 -- 5541},
  year      = {2017},
  abstract  = {We propose a solution based on networks of picture processors to the problem of picture pattern matching. The network solving the problem can be informally described as follows: it consists of two subnetworks, one of them extracts at each step, simultaneously, all subpictures of identical (progressively decreasing) size from the input picture and sends them to the other subnetwork which checks whether any of the received pictures is identical to the pattern. We present an efficient solution based on networks with evolutionary processors only, for patterns with at most three rows or columns. Afterward, we present a solution based on networks containing both evolutionary and hiding processors running in O(n + m + kl) computational (processing and communication) steps, for any size (n, m) of the input pic-ture and (k, l) of the pattern. From the proofs of these results, we infer that any (k, l)-local language with 1 <= k <= 3 can be decided in O(n + m + l) computational steps by networks with evolutionary processors only, while any (k, l)-local language with arbitrary k, l can be decided in O(n + m + kl) computational steps by networks containing both evolutionary and hiding processors.},
  language  = {en}
}
@article{BordihnVaszil2020,
  author    = {Bordihn, Henning and Vaszil, Gy{\"o}rgy},
  title     = {Deterministic Lindenmayer systems with dynamic control of parallelism},
  series = {International journal of foundations of computer science},
  volume    = {31},
  journal   = {International journal of foundations of computer science},
  number    = {1},
  publisher = {World Scientific},
  address   = {Singapore},
  issn      = {0129-0541},
  doi       = {10.1142/S0129054120400031},
  pages     = {37 -- 51},
  year      = {2020},
  abstract  = {M-rate 0L systems are interactionless Lindenmayer systems together with a function assigning to every string a set of multisets of productions that may be applied simultaneously to the string. Some questions that have been left open in the forerunner papers are examined, and the computational power of deterministic M-rate 0L systems is investigated, where also tabled and extended variants are taken into consideration.},
  language  = {en}
}
@article{BenschBordihnHolzeretal.2009,
  author    = {Bensch, Suna and Bordihn, Henning and Holzer, Markus and Kutrib, Martin},
  title     = {On input-revolving deterministic and nondeterministic finite automata},
  issn      = {0890-5401},
  doi       = {10.1016/J.Ic.2009.03.002},
  year      = {2009},
  abstract  = {We introduce and investigate input-revolving finite automata, which are (nondeterministic) finite state automata with the additional ability to shift the remaining part of the input. Three different modes of shifting are considered, namely revolving to the left, revolving to the right, and circular-interchanging. We investigate the computational capacities of these three types of automata and their deterministic variants, comparing any of the six classes of automata with each other and with further classes of well-known automata. In particular, it is shown that nondeterminism is better than determinism, that is, for all three modes of shifting there is a language accepted by the nondeterministic model but not accepted by any deterministic automaton of the same type. Concerning the closure properties most of the deterministic language families studied are not closed under standard operations. For example, we show that the family of languages accepted by deterministic right-revolving finite automata is an anti-AFL which is not closed under reversal and intersection.},
  language  = {en}
}