Skip to main content
Top

2016 | Book

Descriptional Complexity of Formal Systems

18th IFIP WG 1.2 International Conference, DCFS 2016, Bucharest, Romania, July 5-8, 2016. Proceedings

insite
SEARCH

About this book

his book constitutes the refereed proceedings of the 18th International Conference on Descriptional Complexity of Formal Systems, DCFS 2016, held in Bucharest, Romania, in July 2016. The 13 full papers presented together with 4 invited talks were carefully reviewed and selected from 21 submissions.Descriptional Complexity is a field in Computer Science that deals with the size of all kind of objects that occur in computational models, such as Turing Machines, finte automata, grammars, splicing systems and others. The topics of this conference are related to all aspects of descriptional complexity.

Table of Contents

Frontmatter
Completely Reachable Automata
Abstract
We present a few results and several open problems concerning complete deterministic finite automata in which every non-empty subset of the state set occurs as the image of the whole state set under the action of a suitable input word.
Eugenija A. Bondar, Mikhail V. Volkov
Heapability, Interactive Particle Systems, Partial Orders: Results and Open Problems
Abstract
We outline results and open problems concerning partitioning of integer sequences and partial orders into heapable subsequences (previously defined and established by Byers et al.).
Gabriel Istrate, Cosmin Bonchiş
Self-Verifying Finite Automata and Descriptional Complexity
Abstract
We survey recent results on the descriptional complexity of self-verifying finite automata. In particular, we discuss the cost of simulation of self-verifying finite automata by deterministic finite automata, and the complexity of basic regular operations on languages represented by self-verifying finite automata.
Galina Jirásková
On the State Complexity of Partial Derivative Automata For Regular Expressions with Intersection
Abstract
Extended regular expressions (with complement and intersection) are used in many applications due to their succinctness. In particular, regular expressions extended with intersection only (also called semi-extended) can already be exponentially smaller than standard regular expressions or equivalent nondeterministic finite automata (NFA). For practical purposes it is important to study the average behaviour of conversions between these models. In this paper, we focus on the conversion of regular expressions with intersection to nondeterministic finite automata, using partial derivatives and the notion of support. First, we give a tight upper bound of \(2^{O(n)}\) for the worst-case number of states of the resulting partial derivative automaton, where n is the size of the expression. Using the framework of analytic combinatorics, we then establish an upper bound of \((1.056 +o(1))^n\) for its asymptotic average-state complexity, which is significantly smaller than the one for the worst case.
Rafaela Bastos, Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis
Unrestricted State Complexity of Binary Operations on Regular Languages
Abstract
I study the state complexity of binary operations on regular languages over different alphabets. It is well known that if \(L'_m\) and \(L_n\) are languages restricted to be over the same alphabet, with m and n quotients, respectively, the state complexity of any binary boolean operation on \(L'_m\) and \(L_n\) is mn, and that of the product (concatenation) is \((m-1)2^n +2^{n-1}\). In contrast to this, I show that if \(L'_m\) and \(L_n\) are over their own different alphabets, the state complexity of union and symmetric difference is \(mn+m+n+1\), that of intersection is \(mn+1\), that of difference is \(mn+m+1\), and that of the product is \(m2^n+2^{n-1}\).
Janusz Brzozowski
On the State Complexity of the Shuffle of Regular Languages
Abstract
We investigate the shuffle operation on regular languages represented by complete deterministic finite automata. We prove that \(f(m,n)=2^{mn-1} + 2^{(m-1)(n-1)}(2^{m-1}-1)(2^{n-1}-1)\) is an upper bound on the state complexity of the shuffle of two regular languages having state complexities m and n, respectively. We also state partial results about the tightness of this bound. We show that there exist witness languages meeting the bound if \(2\leqslant m\leqslant 5\) and \(n\geqslant 2\), and also if \(m=n=6\). Moreover, we prove that in the subset automaton of the NFA accepting the shuffle, all \(2^{mn}\) states can be distinguishable, and an alphabet of size three suffices for that. It follows that the bound can be met if all f(mn) states are reachable. We know that an alphabet of size at least mn is required provided that \(m,n \geqslant 2\). The question of reachability, and hence also of the tightness of the bound f(mn) in general, remains open.
Janusz Brzozowski, Galina Jirásková, Bo Liu, Aayush Rajasekaran, Marek Szykuła
MSO-definable Properties of Muller Context-Free Languages Are Decidable
Abstract
We show that it is decidable given an MSO-definable property P of countable words and a Muller context-free grammar G, whether every word in the language generated by G satisfies P.
Zoltán Ésik, Szabolcs Iván
Contextual Array Grammars with Matrix and Regular Control
Abstract
We investigate the computational power of d-dimensional contextual array grammars with matrix control and regular control languages. For \(d\ge 2\), d-dimensional contextual array grammars are less powerful than matrix contextual array grammars, which themselves are less powerful than contextual array grammars with regular control languages. Yet in the 1-dimensional case, for a one-letter alphabet, the family of 1-dimensional array languages generated by contextual array grammars with regular control languages coincides with the family of regular 1-dimensional array languages, whereas for alphabets with more than one letter, we obtain the array images of the linear languages.
Henning Fernau, Rudolf Freund, Rani Siromoney, K. G. Subramanian
Descriptional Complexity of Graph-Controlled Insertion-Deletion Systems
Abstract
We consider graph-controlled insertion-deletion systems and prove that the systems with sizes (i) (3; 1, 1, 1; 1, 0, 1), (ii) \((3;1,1,1;1,1,0)\) and (iii) (2; 2, 0, 0; 1, 1, 1) are computationally complete. Moreover, graph-controlled insertion-deletion systems simulate linear languages with sizes (2; 2, 0, 1, 1, 0, 0), (2; 2, 1, 0; 1, 0, 0), (3; 1, 0, 1; 1, 0, 0), or (3; 1, 1, 0; 1, 0, 0). Simulations of metalinear languages are also studied. The parameters in the size \((k;n,i',i'';m,j',j'')\) of a graph-controlled insertion-deletion system denote (from left to right) the maximum number of components, the maximal length of the insertion string, the maximal length of the left context for insertion, the maximal length of the right context for insertion; a similar list of three parameters concerning deletion follows.
Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman
Operations on Weakly Recognizing Morphisms
Abstract
Weakly recognizing morphisms from free semigroups onto finite semigroups are a classical way for defining the class of \(\omega \)-regular languages, i.e., a set of infinite words is weakly recognizable by such a morphism if and only if it is accepted by some Büchi automaton. We consider the descriptional complexity of various constructions for weakly recognizing morphisms. This includes the conversion from and to Büchi automata, the conversion into strongly recognizing morphisms, and complementation. For some problems, we are able to give more precise bounds in the case of binary alphabets or simple semigroups.
Lukas Fleischer, Manfred Kufleitner
Descriptional Complexity of Bounded Regular Languages
Abstract
We investigate the descriptional complexity of the subregular language classes of (strongly) bounded regular languages. In the first part, we study the costs for the determinization of nondeterministic finite automata accepting strongly bounded regular languages. The upper bound for the costs is larger than the costs for determinizing unary regular languages, but lower than the costs for determinizing arbitrary regular languages. In the second part, we study for (strongly) bounded languages the deterministic operational state complexity of the Boolean operations as well as the operations reversal, concatenation, and iteration. In detail, we present upper and lower bounds and we develop for the proof of the lower bounds a tool that exploits the number of different colorings of cycles occurring in deterministic finite automata accepting bounded languages.
Andrea Herrmann, Martin Kutrib, Andreas Malcher, Matthias Wendlandt
The Complexity of Languages Resulting from the Concatenation Operation
Abstract
We prove that for all mn, and \(\alpha \) with \(1 \le \alpha \le f(m,n)\), where f(mn) is the state complexity of the concatenation operation, there exist a minimal m-state DFA A and a minimal n-state DFA B, both defined over an alphabet \(\varSigma \) with \(|\varSigma |\le 2n+4\), such that the minimal DFA for the language L(A)L(B) has exactly \(\alpha \) states. This improves a similar result in the literature that uses an exponential alphabet.
Galina Jirásková, Alexander Szabari, Juraj Šebej
Minimal and Reduced Reversible Automata
Abstract
A condition characterizing the class of regular languages which have several nonisomorphic minimal reversible automata is presented. The condition concerns the structure of the minimum automaton accepting the language under consideration. It is also observed that there exist reduced reversible automata which are not minimal, in the sense that all the automata obtained by merging some of their equivalent states are irreversible. Furthermore, it is proved that if the minimum deterministic automaton accepting a reversible language contains a loop in the “irreversible part” then it is always possible to construct infinitely many reduced reversible automata accepting such a language.
Giovanna J. Lavado, Giovanni Pighizzini, Luca Prigioniero
Unary Self-verifying Symmetric Difference Automata
Abstract
We investigate self-verifying nondeterministic finite automata, in the case of unary symmetric difference nondeterministic finite automata (SV-XNFA). We show that there is a family of languages \(\mathcal {L}_{n\ge 2}\) which can always be represented non-trivially by unary SV-XNFA. We also consider the descriptional complexity of unary SV-XNFA, giving an upper and lower bound for state complexity.
Laurette Marais, Lynette van Zijl
State Complexity of Prefix Distance of Subregular Languages
Abstract
The neighbourhood of a regular language of constant radius with respect to the prefix distance is always regular. We give upper bounds and matching lower bounds for the size of the minimal deterministic finite automaton (DFA) needed for the radius k prefix distance neighbourhood of an n state DFA that recognizes, respectively, a finite, a prefix-closed and a prefix-free language. For prefix-closed languages the lower bound automata are defined over a binary alphabet. For finite and prefix-free regular languages the lower bound constructions use an alphabet that depends on the size of the DFA and it is shown that the size of the alphabet is optimal.
Timothy Ng, David Rappaport, Kai Salomaa
Two Results on Discontinuous Input Processing
Abstract
First, we show that universality and other properties of general jumping finite automata are undecidable, which answers questions asked by Meduna and Zemek in 2012 [12]. Second, we close a study started by Černo and Mráz in 2010 [3] by proving that a clearing restarting automaton using contexts of length two can accept a binary non-context-free language.
Vojtěch Vorel
Backmatter
Metadata
Title
Descriptional Complexity of Formal Systems
Editors
Cezar Câmpeanu
Florin Manea
Jeffrey Shallit
Copyright Year
2016
Electronic ISBN
978-3-319-41114-9
Print ISBN
978-3-319-41113-2
DOI
https://doi.org/10.1007/978-3-319-41114-9

Premium Partner