| Issue |
RAIRO-Theor. Inf. Appl.
Volume 50, Number 3, July-September 2016
|
|
|---|---|---|
| Page(s) | 251 - 261 | |
| DOI | https://doi.org/10.1051/ita/2016024 | |
| Published online | 11 November 2016 | |
Kleene closure and state complexity∗
Mathematical Institute, Slovak Academy of
Sciences, Grešákova
6, 040 01
Košice,
Slovakia
palmovsky@saske.sk
Received:
21
April
2016
Accepted:
14
October
2016
We prove that the automaton presented by Maslov [Soviet Math. Doklady 11 (1970) 1373–1375] meets the upper bound 3/4·2n on the state complexity of Kleene closure. Our main result shows that the upper bounds 2n − 1 + 2n − 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.
Mathematics Subject Classification: 68Q19 / 68Q45
Key words: Regular languages / finite automata / Kleene closure / state complexity
© EDP Sciences 2016
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.