State complexity of power |
| |
Authors: | Michael Domaratzki Alexander Okhotin |
| |
Affiliation: | 1. Department of Computer Science, University of Manitoba, Winnipeg, MB, Canada R3T 2N2;2. Academy of Finland, Helsinki, Finland;3. Department of Mathematics, University of Turku, Turku FIN-20014, Finland |
| |
Abstract: | The number of states in a deterministic finite automaton (DFA) recognizing the language , where is regular language recognized by an -state DFA, and is a constant, is shown to be at most and at least in the worst case, for every and for every alphabet of at least six letters. Thus, the state complexity of is . In the case the corresponding state complexity function for is determined as with the lower bound witnessed by automata over a four-letter alphabet. The nondeterministic state complexity of is demonstrated to be . This bound is shown to be tight over a two-letter alphabet. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|