Search

We investigate the state complexity of languages resulting from the cut operation of two regular languages represented by deterministic finite automata with m and n states, resp. We study the magic number problem of the cut operation and show that the entire range of complexities, up to the known upper bound, can be produced in case of binary alphabets. Moreover, we prove that in the unary case only complexities up to 2m-1 and between n and m+n-2 can be produced, while if 2m

Two-way nondeterministic pushdown automata (2PDA) are classical nondeterministic pushdown automata (PDA) enhanced with two-way motion of the input head. In this paper, the subclass of 2PDA accepting bounded languages and making at most a constant number of input head turns is studied with respect to descriptional complexity aspects. In particular, the effect of reducing the number of pushdown reversals to a constant number is of interest. It turns out that this reduction leads to an exponential blow-up in case of nondeterministic devices, and to a doubly-exponential blow-up in case of deterministic devices. If the restriction on boundedness of the languages considered and on the finiteness of the number of head and pushdown turns is dropped, the resulting trade-offs are no longer bounded by recursive functions, and so-called non-recursive trade-offs are shown.

For each alphabet Σn = {a1,a2,…,an}, linearly ordered by a1 < a2 < ⋯ < an, let Cn be the language of circular or cyclic shifts over Σn, i.e., Cn = {a1a2 ⋯ an-1an, a2a3 ⋯ ana1,…,ana1 ⋯ an-2an-1}. We study a few families of context-free grammars Gn (n ≥1) in Greibach normal form such that Gn generates Cn. The members of these grammar families are investigated with respect to the following descriptional complexity measures: the number of nonterminals ν(n), the number of rules π(n) and the number of leftmost derivations δ(n) of Gn. As in the case of Chomsky normal form, these ν, π and δ are functions bounded by low-degree polynomials. However, the question whether there exists a family of grammars that is minimal w. r. t. all these measures remains open.

Let $\{a_1,a_2,\ldots,a_n\}$ be an alphabet of $n$ symbols and let $C_n$ be the language of circular shifts of the word $a_1a_2\cdots a_n$; so $C_n = \{a_1a_2\cdots a_{n-1}a_n, a_2a_3\cdots a_na_1, \ldots,a_na_1\cdots a_{n-2}a_{n-1}\}$. We discuss a few families of context-free grammars $G_n$ ($n\geq 1$) in Chomsky normal form such that $G_n$ generates $C_n$. The grammars in these families are inverstigated with respect to their descriptional complexity, i.e., we determine the number of nonterminal symbols $\nu(n)$ and the number of rules $\pi(n)$ of $G_n$ as functions of $n$. These $\nu$ and $\pi$ happen to be functions bounded by low-degree polynomials, particularly when we focus our attention to unambiguous grammars. Finally, we introduce a family of minimal unambiguous grammars for which $\nu$ and $\pi$ are linear.

In this paper, we prove that every recursively enumerable language can be generated by a scattered context grammar with no more than two context-sensitive productions.

Promise problems were mainly studied in quantum automata theory. Here we focus on state complexity of classical automata for promise problems. First, it was known that there is a family of unary promise problems solvable by quantum automata by using a single qubit, but the number of states required by corresponding one-way deterministic automata cannot be bounded by a constant. For this family, we show that even two-way nondeterminism does not help to save a single state. By comparing this with the corresponding state complexity of alternating machines, we then get a tight exponential gap between two-way nondeterministic and one-way alternating automata solving unary promise problems. Second, despite of the existing quadratic gap between Las Vegas realtime probabilistic automata and one-way deterministic automata for language recognition, we show that, by turning to promise problems, the tight gap becomes exponential. Last, we show that the situation is different for one-way probabilistic automata with two-sided bounded-error. We present a family of unary promise problems that is very easy for these machines; solvable with only two states, but the number of states in two-way alternating or any simpler automata is not limited by a constant. Moreover, we show that one-way bounded-error probabilistic automata can solve promise problems not solvable at all by any other classical model., 21 pages, significantly improved with a correction (the single sentence statement given just before Corollary 4 in the previous version and (in the conference version) is not correct). A preliminary version appeared in DCFS2014 [vol. 8614 of LNCS, pp. 126--137, Springer-Verlag, 2014]

A sweeping automaton is a two-way deterministic finite automaton which makes turns only at the endmarkers. We say that a sweeping automaton is degenerate if the automaton has no left-moving transitions. We show that for each positive integer n, there is a nondeterministic finite automaton An over a two-letter alphabet such that An has n states, whereas the smallest equivalent nondegenerate sweeping automaton has 2n states.

We consider the class of parallel rewriting systems and investigate the interaction between two complexity measures, that in the literature have been called synchronized parallelism and independent parallelism. It is shown that, when the degree of synchronized parallelism is bounded by some constant greater than one, the degree of independent parallelism induces an infinite non-collapsing hierarchy within the family of generated languages. The result is obtained using an original characterization of parallel rewriting systems. Other language-theoretic properties of parallel rewriting systems are proved in this work, that together with our main result provide an answer to some questions that were left open in the literature.

International audience; A deterministic automaton accepting a regular language L is a state-partition automaton with respect to a projection P if the state set of the deterministic automaton accepting the projected language P(L), obtained by the standard subset construction, forms a partition of the state set of the automaton. In this paper, we study fundamental properties of state-partition automata. We provide a construction of the minimal state-partition automaton for a regular language and a projection, discuss closure properties of state-partition automata under the standard constructions of deterministic automata for regular operations, and show that almost all of them fail to preserve the property of being a state-partition automaton. Finally, we define the notion of a state-partition complexity, and prove the tight bound on the state-partition complexity of regular languages represented by incomplete deterministic automata.

This paper discusses some conditional versions of matrix grammars. It establishes several characterizations of the family of the recursively enumerable languages based on these grammars. In fact, making use of the Geffert Normal forms, the present paper demonstrates these characterizations based on matrix grammars with conditions of a limited length, a reduced number of nonterminals, and a reduced number and size of matrices.

It is well known that the pushdown store language P(M) of a pushdown automaton (PDA) M i.e., the language consisting of words occurring on the pushdownalong accepting computations of M is a regular language. Here, we design succinct nondeterministic finite automata (NFA) accepting P(M). In detail, an upper bound on the size of an NFA for P(M) is obtained, which is quadratic in the number of states and linear in the number of pushdown symbols of M. Moreover, this upper bound is shown to be asymptotically optimal. Then, several restricted variants of PDA are considered, leading to improved constructions. In all cases, we prove the asymptotical optimality of the size of the resulting NFA. Finally, we apply our results to decidability questions related to PDA, and obtain solutions in deterministic polynomial time.

We investigate the conversion of one-way nondeterministic finite automata and context-free grammars into Parikh equivalent one-way and two-way deterministic finite automata, from a descriptional complexity point of view. We prove that for each one-way nondeterministic automaton with $n$ states there exist Parikh equivalent one-way and two-way deterministic automata with $e^{O(\sqrt{n \ln n})}$ and $p(n)$ states, respectively, where $p(n)$ is a polynomial. Furthermore, these costs are tight. In contrast, if all the words accepted by the given automaton contain at least two different letters, then a Parikh equivalent one-way deterministic automaton with a polynomial number of states can be found. Concerning context-free grammars, we prove that for each grammar in Chomsky normal form with h variables there exist Parikh equivalent one-way and two-way deterministic automata with $2^{O(h^2)}$ and $2^{O(h)}$ states, respectively. Even these bounds are tight., Comment: 30 pages, 2 figure. A preliminary version has been presented at DLT 2012, LNCS 7410, pp. 284-295. Version 2: an example has been added in Section 3

We investigate the descriptional complexity of basic operations on real-time one-way cellular automata with an unbounded as well well as a fixed number of cells. The size of the automata is measured by their number of states. Most of the bounds shown are tight in the order of magnitude, that is, the sizes resulting from the effective constructions given are optimal with respect to worst case complexity. Conversely, these bounds also show the maximal savings of size that can be achieved when a given minimal real-time OCA is decomposed into smaller ones with respect to a given operation. From this point of view the natural problem of whether a decomposition can algorithmically be solved is studied. It turns out that all decomposition problems considered are algorithmically unsolvable. Therefore, a very restricted cellular model is studied in the second part of the paper, namely, real-time one-way cellular automata with a fixed number of cells. These devices are known to capture the regular languages and, thus, all the problems being undecidable for general one-way cellular automata become decidable. It is shown that these decision problems are $\textsf{NLOGSPACE}$-complete and thus share the attractive computational complexity of deterministic finite automata. Furthermore, the state complexity of basic operations for these devices is studied and upper and lower bounds are given.

Der Theorietag ist die Jahrestagung der Fachgruppe Automaten und Formale Sprachen der Gesellschaft für Informatik. Er wird seit 1991 von Mitgliedern der Fachgruppe an wechselnden Orten in Deutschland und Österreich veranstaltet. Im Laufe des Theorietags findet auch die jährliche Fachgruppensitzung statt. Seit 1996 wird der Theorietag von einem eintägigen Workshop mit eingeladenen Vorträgen begleitet. Die bisherigen Austragungsorte waren Magdeburg (1991), Kiel (1992), Dagstuhl (1993), Herrsching (1994), Schloß Rauischholzhausen (1995), Cunnersdorf (1996), Barnstorf (1997), Riveris (1998), Schauenburg-Elmshagen (1999), Wien (2000), Wendgräben (2001), Wittenberg (2002), Herrsching (2003), Caputh (2004),Lauterbad (2005), Wien (2006) und Leipzig (2007). Der diesjährige Theorietag wird nach 13 Jahren wieder vom Institut für Informatik der Justus-Liebig-Universität Gießen ausgerichtet. Er findet mit dem vorangestellten Workshop über Selected Topics in Theoretical Computer Science vom 30. September bis zum 2. Oktober 2008 in Wettenberg-Launsbach bei Gießen statt. Teilnehmer aus Belgien, Deutschland, England, Frankreich, Italien, Österreich, Tschechien und Ungarn folgten der Einladung nach Mittelhessen.

Der Theorietag ist die Jahrestagung der Fachgruppe Automaten und Formale Sprachen der Gesellschaft für Informatik. Er wird seit 1991 von Mitgliedern der Fachgruppe an wechselnden Orten in Deutschland und Österreich veranstaltet. Im Laufe des Theorietags findet auch die jährliche Fachgruppensitzung statt. Seit 1996 wird der Theorietag von einem eintägigen Workshop mit eingeladenen Vorträgen begleitet. Die bisherigen Aus- tragungsorte waren Magdeburg (1991), Kiel (1992), Dagstuhl (1993), Herrsching (1994), Schloß Rauischholzhausen (1995), Cunnersdorf (1996), Barn- storf (1997), Riveris (1998), Schauenburg-Elmshagen (1999), Wien (2000), Wendgräben (2001), Wittenberg (2002), Herrsching (2003), Caputh (2004), Lauterbad (2005), Wien (2006) und Leipzig (2007). Der diesjährige Theorietag wird nach 13 Jahren wieder vom Institut für Informatik der Justus-Liebig-Universität Gießen ausgerichtet. Er findet mit dem vorangestellten Workshop über Selected Topics in Theoretical Computer Science vom 30. September bis zum 2. Oktober 2008 in Wettenberg- Launsbach bei Gießen statt. Teilnehmer aus Belgien, Deutschland, England, Frankreich, Italien, Österreich, Tschechien und Ungarn folgten der Einladung nach Mittelhessen.

Das Modell der Restart-Automaten gibt es seit etwa 15 Jahren. Durch die Ausstattung mit verschiedenen Berechnungsressourcen und die Auferlegung von Einschränkungen an die Arbeitsweise entstand mit der Zeit ein unfangreiches System von Automatentypen mit stark unterschiedlicher generativer Mächtigkeit. Ziel dieser Arbeit ist es, Restart-Automaten in ihrer Effizienz bei der Beschreibung von Sprachen mit der von konventionellen Automatenmodellen und Grammatiken, sowie untereinander, zu vergleichen. Die Schwerpunkte liegen zum einen auf dem Vergleich von Beschreibern regulärer Sprachen (Zustandskomplexität) und zum anderen auf dem Nachweis nichtrekursiver trade-offs (in Bezug auf die Beschreibungskomplexität) zwischen den mächtigeren Sprachklassen. Im Rahmen des ersten Schwerpunkts werden die Systeme NFA, DFA, AFA (nichtdeterministische, deterministische und alternierende endliche Automaten) mit den beiden Restart-Automaten-Typen R(1) und det-RR(1) verglichen, die ebenfalls Akzeptoren für reguläre Sprachen sind (der Nachweis dieser Eigenschaft von det-RR(1)-Automaten ist ebenfalls Bestandteil dieser Arbeit). Für die Untersuchungen im Rahmen des zweiten Schwerpunkts werden zusätzlich einige Nachweise bezüglich der (Nicht-)Erkennung von valid-computations Sprachen, sowie einiger nicht-semi-entscheidbarer Eigenschaften geführt., Restarting automata have been studied for approximately 15 years. The use of different computational ressources, combined with restrictions on the process of recognition yields a variety of sub-types of different computational capacity. Our main goal lies in studying the descriptional efficiency of these models. Comparisons are made between different types of restarting automata and towards well-known automaton models and grammars. The results fall in two categories: the first of them is the descriptional complexity of acceptors of regular languages (state complexity) and the second one consists of proofs of non-recursive trade-offs (in descriptional complexity) between more powerful descriptional systems. For the first category, the formal models NFA, DFA, AFA (non-deterministic, deterministic and alternating finite automata) are compared to the two types of restarting automata named R(1) and det-RR(1), respectively. These latter two also characterise the class of regular languages (the proof for det-RR(1)-automata is included here). To obtain results of the second category, several additional proofs concerning (non-)acceptance of valid-computations languages and non-semi-decidable properties are given.

Let $\{a_1,a_2,\ldots,a_n\}$ be an alphabet of $n$ symbols and let $C_n$ be the language of circular shifts of the word $a_1a_2\cdots a_n$; so $C_n = \{a_1a_2\cdots a_{n-1}a_n, a_2a_3\cdots a_na_1, \ldots,a_na_1\cdots a_{n-2}a_{n-1}\}$. We discuss a few families of context-free grammars $G_n$ ($n\geq 1$) in Chomsky normal form such that $G_n$ generates $C_n$. The grammars in these families are inverstigated with respect to their descriptional complexity, i.e., we determine the number of nonterminal symbols $\nu(n)$ and the number of rules $\pi(n)$ of $G_n$ as functions of $n$. These $\nu$ and $\pi$ happen to be functions bounded by low-degree polynomials, particularly when we focus our attention to unambiguous grammars. Finally, we introduce a family of minimal unambiguous grammars for which $\nu$ and $\pi$ are linear.

Let $\{a_1,a_2,\ldots,a_n\}$ be an alphabet of $n$ symbols and let $C_n$ be the language of circular shifts of the word $a_1a_2\cdots a_n$; so $C_n = \{a_1a_2\cdots a_{n-1}a_n, a_2a_3\cdots a_na_1, \ldots,a_na_1\cdots a_{n-2}a_{n-1}\}$. We discuss a few families of context-free grammars $G_n$ ($n\geq 1$) in Chomsky normal form such that $G_n$ generates $C_n$. The grammars in these families are inverstigated with respect to their descriptional complexity, i.e., we determine the number of nonterminal symbols $\nu(n)$ and the number of rules $\pi(n)$ of $G_n$ as functions of $n$. These $\nu$ and $\pi$ happen to be functions bounded by low-degree polynomials, particularly when we focus our attention to unambiguous grammars. Finally, we introduce a family of minimal unambiguous grammars for which $\nu$ and $\pi$ are linear.

Let $\{a_1,a_2,\ldots,a_n\}$ be an alphabet of $n$ symbols and let $C_n$ be the language of circular shifts of the word $a_1a_2\cdots a_n$; so $C_n = \{a_1a_2\cdots a_{n-1}a_n, a_2a_3\cdots a_na_1, \ldots,a_na_1\cdots a_{n-2}a_{n-1}\}$. We discuss a few families of context-free grammars $G_n$ ($n\geq 1$) in Chomsky normal form such that $G_n$ generates $C_n$. The grammars in these families are inverstigated with respect to their descriptional complexity, i.e., we determine the number of nonterminal symbols $\nu(n)$ and the number of rules $\pi(n)$ of $G_n$ as functions of $n$. These $\nu$ and $\pi$ happen to be functions bounded by low-degree polynomials, particularly when we focus our attention to unambiguous grammars. Finally, we introduce a family of minimal unambiguous grammars for which $\nu$ and $\pi$ are linear.

Parallel communicating grammar systems (PC grammar systems, in short) are language generating devices consisting of several context-free grammars which work synchronously on their own sentential forms and communicate the generated strings to each other by request. These systems with eleven components are known to have the power of the Turing machines. We considerably improve this result, proving that five components suffice in order to generate any recursively enumerable language.

Over the last 30 years or so many results have appeared on the descriptional complexity of machines with limited resources. Since these results have appeared in a variety of different contexts, our goal here is to provide a survey of these results. Particular emphasis is put on limiting resources (e.g., nondeterminism, ambiguity, lookahead, etc.) for various types of finite state machines, pushdown automata, parsers and cellular automata and on the effect it has on their descriptional complexity. We also address the question of how descriptional complexity might help in the future to solve practical issues, such as software reliability. 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.

We investigate the nondeterministic state complexity of several operations on finite automata accepting star-free and unary star-free languages. It turns out that in most cases exactly the same tight bounds as for general regular languages are reached. This nicely complements the results recently obtained by Brzozowski and Liu (2011) [8] for the operation problem of star-free and unary star-free languages accepted by deterministic finite automata.

In this paper, we consider two tradeoff results regarding the economy of description in parsing. One result is on the tradeoff between the size of a parser and its ability to detect an error early. The other result is on the tradeoff between the size of an LR(k)-grammar and the length k of the lookahead.

A transition is unobservable if it is labeled by a symbol removed by a projection. The present paper investigates a new structural property of incomplete deterministic finite automata–a number of states incident with an unobservable transition–and its effect on the state complexity of projected regular languages. We show that the known upper bound can be met only by automata with one unobservable transition (up to unobservable multi-transitions). We improve this upper bound by taking into consideration the structural property of minimal incomplete automata, and prove the tightness of new upper bounds. Special attention is focused on the case of finite languages. The paper also presents and discusses several fundamental problems which are still open.