Search

In this paper, we start a systematic study of the number of accepting states. For a regular language $L$, we define the complexity $\asc(L)$ as the minimal number of accepting states necessary to accept $L$ by deterministic finite automata. With respect to nondeterministic automata, the corresponding measure is $\nasc(L)$. We prove that, for any non-negative integer $n$, there is a regular language $L$ such that $\asc(L)=n$, whereas we have $\nasc(R)\leq 2$ for any regular language $R$. Moreover, for a $k$-ary regularity preserving operation $\circ$ on languages, we define $g_{\circ}^{\asc}(n_1,n_2,\dots ,n_k)$ as the set of all integers~$r$ such that there are $k$ regular languages $L_i$, $1\leq i\leq k$, such that $\asc(L_i)=n_i$ for $1\leq i\leq k$ and $\asc(\circ(L_1,L_2,\dots ,L_k))=r$. We determine this set for the operations complement, union, product, Kleene closure, and set difference., Journal of Automata, Languages and Combinatorics, Volume 21, Numbers 1-2, 2016, 55-67

Editorial of the last issue of the journal which has been published by the Otto-von-Guericke-Universität Magdeburg for 20 years., Journal of Automata, Languages and Combinatorics, Volume 20, Number 1, 2015, 3-4

Editorial to the special issues dedicated to Professor Dr. Erzsébet Csuhaj-Varjú on the occasion of her birthday. They contain articles on recent research in the theory of automata, formal languages, networks of language processors, bio-inspired models of computations, membrane computing, P automata, grammar systems, grammars with regulated rewriting, descriptional complexity of automata/networks/systems, multi-tape automata, multi-dimensional grammars, combinatorics on words. The contributing authors -- leading researchers, colleagues, and friends -- honour Erzsébet Csuhaj-Varjú with papers in fields where she has been and still is very active., Journal of Automata, Languages and Combinatorics, Volume 19, Numbers 1-4, 2014, 3-4

We extend the edit operators of substitution, deletion, and insertion of a symbol over a word by introducing two new operators (partial copy and partial elimination) inspired by biological gene duplication. We de ne a disruption measure for an operator over a word and prove that whereas the traditional edit operators are disruptive, partial copy and partial elimination are non-disruptive. Moreover, we show that the application of only edit operators does not generate (with low disruption) all the words over a binary alphabet, but this can indeed be done by combining partial copy and partial elimination with the substitution operator. Universidad de Málaga. Campus de Excelencia Internacional Andalucía Tech.

Journal of Automata, Languages and Combinatorics, Volume 17, Numbers 2-4, 2012, 59-60

We investigate context-free languages with respect to the measures Prod and Symb of descriptional complexity, which give the minimal number of productions and the minimal total number of symbols in productions, respectively, necessary to generate the language by context-free grammars. In particular, we consider the behaviour of these measures with respect to operations. For a measure $K\in \{\Prod,\Symb\}$, given natural numbers $c_1,c_2,\dots ,c_n$ and an $n$-ary operation $\tau$ on languages, we discuss the set $g_{\tau,K}(c_1,c_2,\dots ,c_n)$ which is the range of $K(\tau(L_1,L_2,\dots , L_n))$ where, for $1\leq i\leq n$, $L_i$ is a context-free language with $K(L_i)=c_i$. The operations under discussion are union and Kleene closure., Journal of Automata, Languages and Combinatorics, Volume 17, Numbers 2-4, 2012, 123-143

In this paper, we study the power of internal contextual grammars with selection languages from subfamilies of the family of regular languages. If we consider families ${\cal F}_n$ which are obtained by restriction to $n$ states, nonterminals, productions, or symbols to accept or to generate a regular language, we obtain four infinite hierarchies of the corresponding families of languages generated by internal contextual grammars with selection languages in ${\cal F}_n$. Moreover, we present some results on the power of internal contextual grammars with finite, monoidal, nilpotent, combinational, definite, ordered, regular commutative, regular circular, regular suffix-closed, and union-free selection languages., Journal of Automata, Languages and Combinatorics, Volume 17, Numbers 2-4, 2012, 145-164

Multicellular organisms undergo a complex developmental process, orchestrated by the genetic information in their cells, in order to form a newborn individual from a fertilized egg. This complex process, not completely understood yet, is believed to have a key role in generating the impressive biotic diversity of organisms found on earth. Inspired by mechanisms of Eukaryotic genetic expression, we propose and analyse graph grammars with string-regulated rewriting. In these grammatical systems a genome sequence is represented by a regulatory string, a graph corresponds to an organism, and a set of graph grammar rules represents different forms of implementing cell division. Accordingly, a graph derivation by the graph grammar resembles the developmental process of an organism. We give examples of the concept and compare its generative power to the power of the traditional context-free graph grammars. We demonstrate that the power of expression increases when genetic regulation is included in the model, as compared to non-regulated grammars. Additionally, we propose a hierarchy of string-regulated graph grammars, arranged by expressive power. These results highlight the key role that the transmission of regulatory information during development has in the emergence of biological diversity. D.L. was supported in part by a research stay fellowship at Otto-von-Guericke-Universität Magdeburg from the Spanish Ministerio de Educación.

Journal of Automata, Languages and Combinatorics, Volume 16, Numbers 2-4, 2011, 71-74

Journal of Automata, Languages and Combinatorics, Volume 15, Numbers 1-2, 2010, 5-5

Journal of Automata, Languages and Combinatorics, Volume 14, Number 1, 2009, 5-6

Membrane or P systems form a distributed parallel model of computing which is obtained as an abstraction from the structure and functioning of living cells. In this paper we consider a very basic membrane system and add to it checkers which are special finite automata to check whether or not a configuration of the membrane system is "good" or "bad". The computation is only continued if the configuration is good, otherwise it stops without a result. Such membrane systems are called Darwinian P systems. There are three parameters characterizing the size of a system, the number of membranes, the number of checkers, and the size of the checkers measured by the number of states. We prove that we can generate all sets of Parikh vectors of recursively enumerable languages if we restrict the number and size of checkers to one checker with six states or to five checkers with two states. Moreover, we prove that Darwinian systems with one membrane and checkers with at most two states are also sufficient to generate all Parikh sets of recursively enumerable languages. The latter result is optimal since Darwinian systems with checkers with only one state generate only sets of Parikh vectors of ET0L languages. All results are valid for length sets instead of sets of Parikh vectors, too.

Journal of Automata, Languages and Combinatorics, Volume 9, Numbers 2-3, 2004, 173-173

Journal of Automata, Languages and Combinatorics, Volume 8, Number 1, 2003, 3-4

Journal of Automata, Languages and Combinatorics, Volume 7, Number 4, 2002, 417-417

With any Petri net we associated its CPN language which consists of all sequences of transitions which reach a marking with an empty place whereas all proper prefixes of the sequence lead to positive markings. We prove that any CPN language can be accepted by a partially blind multicounter machine, and that any partially blind multicounter language is the morphic image of some CPN language. As a corollary we obtain the decidability of membership, emptiness and finiteness problem for CPN languages. We characterize the very strictly bounded regular languages, which are CPN languages, and give a condition for a Petri net, which ensures that its generated language is regular. We give a dense CPN language and prove that no dense regular language is a CPN language. 1.) C. S. Calude, K. Salomaa, S. Yu (eds.). Advances and Trends in Automata and Formal Languages. A Collection of Papers in Honour of the 60th Birthday of Helmut Jürgensen.