Geodesic
Kleene closure and state complexity
Palmovský, Matúš1
1 Mathematical Institute, Slovak Academy of Sciences, Grešákova 6, 040 01 Košice, Slovakia
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 50 (2016) no. 3, pp. 251-261

Voir la notice de l'article provenant de la source Numdam

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≤k≤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.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2016024
Classification : 68Q19, 68Q45
Keywords: 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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :