Kleene closure and state complexity

Palmovský, Matúš

doi:10.1051/ita/2016024

Geodesic

Parcourir par

Kleene closure and state complexity

Palmovský, Matúš ¹

¹ 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

Résumé

We prove that the automaton presented by Maslov [Soviet Math. Doklady 11 (1970) 1373–1375] meets the upper bound $3 / 4 \cdot 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 \leq k \leq 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 : 2016-04-21
Accepté le : 2016-10-14

MR Zbl

DOI : 10.1051/ita/2016024

Classification : 68Q19, 68Q45
Keywords: Regular languages, finite automata, Kleene closure, state complexity

Affiliations des auteurs :

Palmovský, Matúš ¹

¹ 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 :