@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{BordihnHolzerKutrib2009,
  author    = {Bordihn, Henning and Holzer, Markus and Kutrib, Martin},
  title     = {Determination of finite automata accepting subregular languages},
  issn      = {0304-3975},
  doi       = {10.1016/j.tcs.2009.05.019},
  year      = {2009},
  abstract  = {We investigate the descriptional complexity of the nondeterministic finite automaton (NFA) to the deterministic finite automaton (DFA) conversion problem, for automata accepting subregular languages such as combinational languages, definite languages and variants thereof, (strictly) locally testable languages, star-free languages, ordered languages, prefix-, suffix-, and infix-closed languages, and prefix-, Suffix-, and infix-free languages. Most of the bounds for the conversion problem are shown to be tight ill the exact number of states, that is, the number is sufficient and necessary in the worst case. Otherwise tight bounds in order of magnitude are shown.},
  language  = {en}
}
@article{BordihnDassowHolzer2010,
  author    = {Bordihn, Henning and Dassow, Juergen and Holzer, Markus},
  title     = {Extending regular expressions with homomorphic replacement},
  issn      = {0988-3754},
  doi       = {10.1051/Ita/2010013},
  year      = {2010},
  abstract  = {We define H- and EH-expressions as extensions of regular expressions by adding homomorphic and iterated homomorphic replacement as new operations, resp. The definition is analogous to the extension given by Gruska in order to characterize context-free languages. We compare the families of languages obtained by these extensions with the families of regular, linear context-free, context-free, and EDT0L languages. Moreover, relations to language families based on patterns, multi-patterns, pattern expressions, H-systems and uniform substitutions are also investigated. Furthermore, we present their closure properties with respect to TRIO operations and discuss the decidability status and complexity of fixed and general membership, emptiness, and the equivalence problem.},
  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}
}
@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}
}
@article{BordihnHolzer2021,
  author    = {Bordihn, Henning and Holzer, Markus},
  title     = {On the number of active states in finite automata},
  series = {Acta informatica},
  volume    = {58},
  journal   = {Acta informatica},
  number    = {4},
  publisher = {Springer},
  address   = {Berlin ; Heidelberg [u.a.]},
  issn      = {0001-5903},
  doi       = {10.1007/s00236-021-00397-8},
  pages     = {301 -- 318},
  year      = {2021},
  abstract  = {We introduce a new measure of descriptional complexity on finite automata, called the number of active states. Roughly speaking, the number of active states of an automaton A on input w counts the number of different states visited during the most economic computation of the automaton A for the word w. This concept generalizes to finite automata and regular languages in a straightforward way. We show that the number of active states of both finite automata and regular languages is computable, even with respect to nondeterministic finite automata. We further compare the number of active states to related measures for regular languages. In particular, we show incomparability to the radius of regular languages and that the difference between the number of active states and the total number of states needed in finite automata for a regular language can be of exponential order.},
  language  = {en}
}
@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{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}
}