Kleene closure and state complexity

Palmovský, Matúš

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 50 (2016) no. 3, pp. 251-261.

We prove that the automaton presented by Maslov [Soviet Math. Doklady 11 (1970) 1373–1375] meets the upper bound $3/4·2^n$ on the state complexity of Kleene closure. Our main result shows that the upper bounds $2^{n-1}+2^{n-1-k}$ on the state complexity of Kleene closure of a language accepted by an $n$-state DFA with $k$ final states are tight for every $k$ with $1\le k\le n$ in the binary case. We also study Kleene Closure on prefix-free languages. In the case of prefix-free languages, the Kleene closure may attain just three possible complexities $n-2,n-1,$ and $n$. We give some survey of our computations.

Classification : 68Q19, 68Q45
Mots clés : Regular languages, finite automata, Kleene closure, state complexity

J.A. Brzozowski, In search of most complex regular languages. Internat. J. Found. Comput. Sci. 24 (2013) 691–708. | DOI | MR | Zbl

J.A. Brzozowski, E. Leiss, On equations for regular languages, finite automata, and sequential networks. Theoret. Comput. Sci. 10 (1980) 19–35. | DOI | MR | Zbl

K. Čevorová, Kleene star on unary regular languages. DCFS 2013, edited by H. Jürgensen, R. Reis. In vol. 8031 of Lect. Notes Comput. Sci. Springer (2013) 277–288. | MR

Y. Gao, L. Kari, S. Yu, State complexity of union and intersection of star on k regular languages. Theoret. Comput. Sci. 429 (2012) 98–107. | DOI | MR | Zbl

Y. Gao, N. Moreira, R. Reis, S. Yu, A review on state complexity of individual operations. Technical report, Technical Report Series DCC-2011-08, Version 1.1 Universidade do Porto. Available at www.dcc.fc.up.pt/Pubs (2016).

V. Geffert, Magic numbers in the state hierarchy of finite automata. Inform. Comput. 205 (2007) 1652–1670. | DOI | MR | Zbl

J. Hopcroft, An $nlogn$ algorithm for minimizing states in A finite automata. Technical Report STAN-CS-71-190. Computer Science Dept. (1971).

Y.S. Han, K. Salomaa, D. Wood, Operational state complexity of prefix-free regular languages. Automata, Formal Languages, and Related Topics. Institute of Informatics, University of Szeged (2009) 99–115. | MR | Zbl

K. Iwama, Y. Kambayashi, K. Takaki, Tight bounds on the number of states of DFAs that are equivalent to $n$-state NFAs. Theoret. Comput. Sci. 237 (2000) 485–494. Preliminary version in: 3rd International Conference on Developments in Language Theory, edited by S. Bozapalidis. Aristotle University of Thessaloniki (1997). | DOI | MR | Zbl

G. Jirásková, The Ranges of state complexities for complement, star, and reversal of regular languages. Internat. J. Found. Comput. Sci. 25 (2014) 101–124. Preliminary version: On the state complexity of complements, stars, and reversals of regular languages. DLT 2008, edited by M. Ito, M. Toyama. In vol. 5257 of Lect. Notes Comput. Sci. Springer (2008) 431–442. | DOI | Zbl

G. Jirásková, Magic numbers and ternary alphabet. Int. J. Found. Comput. Sci. 22 (2011) 331–344. | DOI | MR | Zbl

G. Jirásková, M. Palmovský, J.S. Šebej, Kleene Closure on Regular and Prefix-Free Languages. CIAA 2014, edited by M. Holzer, M. Kutrib. In vol. 8587 of Lect. Notes Comput. Sci. Springer (2014) 226–237. | MR | Zbl

A.N. Maslov, Estimates of the number of states of finite automata. Soviet Math. Doklady 11 (1970) 1373–1375. | MR | Zbl

M. Sipser, Introduction to the theory of computation. PWS Publishing Company, Boston (1997). | Zbl

M. Rabin, D. Scott, Finite automata and their decision problems. IBM Res. Develop. 3 (1959) 114–129. | DOI | MR | Zbl

J. Šebej, Reversal of regular language and state complexity. Master’s thesis. P.J. Šafárik University in Košice, Slovakia (2012).

S. Yu, Regular languages, Chapter 2. In vol. I of Handbook of Formal Languages, edited by G. Rozenberg, A. Salomaa. Springer, Heidelberg (1997) 41–110. | MR | Zbl

S. Yu, Q. Zhuang, K. Salomaa, The state complexity of some basic operations on regular languages. Theoret. Comput. Sci. 125 (1994) 315–328. | DOI | MR | Zbl