Kleene closure and state complexity
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 1kn 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.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2016024
Classification : 68Q19, 68Q45
Mots clés : Regular languages, finite automata, Kleene closure, state complexity
Palmovský, Matúš 1

1 Mathematical Institute, Slovak Academy of Sciences, Grešákova 6, 040 01 Košice, Slovakia
@article{ITA_2016__50_3_251_0,
     author = {Palmovsk\'y, Mat\'u\v{s}},
     title = {Kleene closure and state complexity},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {251--261},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {3},
     year = {2016},
     doi = {10.1051/ita/2016024},
     mrnumber = {3582641},
     zbl = {1357.68107},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita/2016024/}
}
TY  - JOUR
AU  - Palmovský, Matúš
TI  - Kleene closure and state complexity
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2016
SP  - 251
EP  - 261
VL  - 50
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita/2016024/
DO  - 10.1051/ita/2016024
LA  - en
ID  - ITA_2016__50_3_251_0
ER  - 
%0 Journal Article
%A Palmovský, Matúš
%T Kleene closure and state complexity
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2016
%P 251-261
%V 50
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita/2016024/
%R 10.1051/ita/2016024
%G en
%F ITA_2016__50_3_251_0
Palmovský, Matúš. Kleene closure and state complexity. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 50 (2016) no. 3, pp. 251-261. doi : 10.1051/ita/2016024. http://archive.numdam.org/articles/10.1051/ita/2016024/

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

Cité par Sources :