@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{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{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} } @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{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} } @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{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{BordihnKutribMalcher2012, author = {Bordihn, Henning and Kutrib, Martin and Malcher, Andreas}, title = {On the computational capacity of parallel communicating finite automata}, series = {International journal of foundations of computer science}, volume = {23}, journal = {International journal of foundations of computer science}, number = {3}, publisher = {World Scientific}, address = {Singapore}, issn = {0129-0541}, doi = {10.1142/S0129054112500062}, pages = {713 -- 732}, year = {2012}, abstract = {Systems of parallel finite automata communicating by states are investigated. We consider deterministic and nondeterministic devices and distinguish four working modes. It is known that systems in the most general mode are as powerful as one-way multi-head finite automata. Here we solve some open problems on the computational capacity of systems working in the remaining modes. In particular, it is shown that deterministic returning and non-returning devices are equivalent, and that there are languages which are accepted by deterministic returning and centralized systems but cannot be accepted by deterministic non-returning centralized systems. Furthermore, we show that nondeterministic systems are strictly more powerful than their deterministic variants in all the four working modes. Finally, incomparability with the classes of (deterministic) (linear) context-free languages as well as the Church-Rosser languages is derived.}, 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} } @article{BordihnMitrana2020, author = {Bordihn, Henning and Mitrana, Victor}, title = {On the degrees of non-regularity and non-context-freeness}, series = {Journal of computer and system sciences}, volume = {108}, journal = {Journal of computer and system sciences}, publisher = {Elsevier}, address = {San Diego, Calif. [u.a.]}, issn = {0022-0000}, doi = {10.1016/j.jcss.2019.09.003}, pages = {104 -- 117}, year = {2020}, abstract = {We study the derivational complexity of context-free and context-sensitive grammars by counting the maximal number of non-regular and non-context-free rules used in a derivation, respectively. The degree of non-regularity/non-context-freeness of a language is the minimum degree of non-regularity/non-context-freeness of context-free/context-sensitive grammars generating it. A language has finite degree of non-regularity iff it is regular. We give a condition for deciding whether the degree of non-regularity of a given unambiguous context-free grammar is finite. The problem becomes undecidable for arbitrary linear context-free grammars. The degree of non-regularity of unambiguous context-free grammars generating non-regular languages as well as that of grammars generating deterministic context-free languages that are not regular is of order Omega(n). Context-free non-regular languages of sublinear degree of non-regularity are presented. A language has finite degree of non-context-freeness if it is context-free. Context-sensitive grammars with a quadratic degree of non-context-freeness are more powerful than those of a linear degree.}, language = {en} } @article{BordihnMitranaNegruetal.2018, author = {Bordihn, Henning and Mitrana, Victor and Negru, Maria C. and Paun, Andrei and Paun, Mihaela}, title = {Small networks of polarized splicing processors are universal}, series = {Natural computing : an innovative journal bridging biosciences and computer sciences ; an international journal}, volume = {17}, journal = {Natural computing : an innovative journal bridging biosciences and computer sciences ; an international journal}, number = {4}, publisher = {Springer}, address = {Dordrecht}, issn = {1567-7818}, doi = {10.1007/s11047-018-9691-0}, pages = {799 -- 809}, year = {2018}, abstract = {In this paper, we consider the computational power of a new variant of networks of splicing processors in which each processor as well as the data navigating throughout the network are now considered to be polarized. While the polarization of every processor is predefined (negative, neutral, positive), the polarization of data is dynamically computed by means of a valuation mapping. Consequently, the protocol of communication is naturally defined by means of this polarization. We show that networks of polarized splicing processors (NPSP) of size 2 are computationally complete, which immediately settles the question of designing computationally complete NPSPs of minimal size. With two more nodes we can simulate every nondeterministic Turing machine without increasing the time complexity. Particularly, we prove that NPSP of size 4 can accept all languages in NP in polynomial time. Furthermore, another computational model that is universal, namely the 2-tag system, can be simulated by NPSP of size 3 preserving the time complexity. All these results can be obtained with NPSPs with valuations in the set as well. We finally show that Turing machines can simulate a variant of NPSPs and discuss the time complexity of this simulation.}, language = {en} } @article{BordihnMitranaPaunetal.2020, author = {Bordihn, Henning and Mitrana, Victor and Paun, Andrei and Paun, Mihaela}, title = {Hairpin completions and reductions}, series = {Natural computing : an innovative journal bridging biosciences and computer sciences ; an international journal}, volume = {20}, journal = {Natural computing : an innovative journal bridging biosciences and computer sciences ; an international journal}, number = {2}, publisher = {Springer Science + Business Media B.V.}, address = {Dordrecht}, issn = {1572-9796}, doi = {10.1007/s11047-020-09797-0}, pages = {193 -- 203}, year = {2020}, abstract = {This paper is part of the investigation of some operations on words and languages with motivations coming from DNA biochemistry, namely three variants of hairpin completion and three variants of hairpin reduction. Since not all the hairpin completions or reductions of semilinear languages remain semilinear, we study sufficient conditions for semilinear languages to preserve their semilinearity property after applying the non-iterated hairpin completion or hairpin reduction. A similar approach is then applied to the iterated variants of these operations. Along these lines, we define the hairpin reduction root of a language and show that the hairpin reduction root of a semilinear language is not necessarily semilinear except the universal language. A few open problems are finally discussed.}, 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{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{BordihnVaszil2021, author = {Bordihn, Henning and Vaszil, Gy{\"o}rgy}, title = {Reversible parallel communicating finite automata systems}, series = {Acta informatica}, volume = {58}, journal = {Acta informatica}, number = {4}, publisher = {Springer}, address = {Berlin ; Heidelberg ; New York, NY}, issn = {0001-5903}, doi = {10.1007/s00236-021-00396-9}, pages = {263 -- 279}, year = {2021}, abstract = {We study the concept of reversibility in connection with parallel communicating systems of finite automata (PCFA in short). We define the notion of reversibility in the case of PCFA (also covering the non-deterministic case) and discuss the relationship of the reversibility of the systems and the reversibility of its components. We show that a system can be reversible with non-reversible components, and the other way around, the reversibility of the components does not necessarily imply the reversibility of the system as a whole. We also investigate the computational power of deterministic centralized reversible PCFA. We show that these very simple types of PCFA (returning or non-returning) can recognize regular languages which cannot be accepted by reversible (deterministic) finite automata, and that they can even accept languages that are not context-free. We also separate the deterministic and non-deterministic variants in the case of systems with non-returning communication. We show that there are languages accepted by non-deterministic centralized PCFA, which cannot be recognized by any deterministic variant of the same type.}, language = {en} } @article{PabloAlarconArroyoBordihnetal.2015, author = {Pablo Alarcon, Pedro and Arroyo, Fernando and Bordihn, Henning and Mitrana, Victor and Mueller, Mike}, title = {Ambiguity of the multiple interpretations on regular languages}, series = {Fundamenta informaticae}, volume = {138}, journal = {Fundamenta informaticae}, number = {1-2}, publisher = {IOS Press}, address = {Amsterdam}, issn = {0169-2968}, doi = {10.3233/FI-2015-1200}, pages = {85 -- 95}, year = {2015}, abstract = {A multiple interpretation scheme is an ordered sequence of morphisms. The ordered multiple interpretation of a word is obtained by concatenating the images of that word in the given order of morphisms. The arbitrary multiple interpretation of a word is the semigroup generated by the images of that word. These interpretations are naturally extended to languages. Four types of ambiguity of multiple interpretation schemata on a language are defined: o-ambiguity, internal ambiguity, weakly external ambiguity and strongly external ambiguity. We investigate the problem of deciding whether a multiple interpretation scheme is ambiguous on regular languages.}, language = {en} }