• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

State Complexity of Power

Michael Domaratzki, Alexander Okhotin, State Complexity of Power. TUCS Technical Reports 845, Turku Centre for Computer Science, 2008.

Abstract:

The number of states in a deterministic finite automaton (DFA)
recognizing the language <i>L</i>^<i>k</i>,
where <i>L</i> is regular language recognized by an <i>n</i>-state DFA,
and <i>k</i> &ge; 2 is a constant,
is shown to be at most <i>n</i> 2^{(<i>k</i>&#8722;1)<i>n</i>}
and at least (<i>n</i>&#8722;<i>k</i>) 2^{(<i>k</i>&#8722;1)(<i>n</i>&#8722;<i>k</i>)} in the worst case,
for every <i>n</i> > <i>k</i>
and for every alphabet of at least six letters.
Thus, the state complexity of L^<i>k</i>
is &Theta;(<i>n</i> 2^{(<i>k</i>&#8722;1)<i>n</i>}).
In the case <i>k</i>=3
the corresponding state complexity function for <i>L</i>³
is determined as
(6<i>n</i>&#8722;3)/8 4^<i>n</i> &#8722; (<i>n</i>&#8722;1)2^<i>n</i> &#8722; <i>n</i>
with the lower bound witnessed by automata over a four-letter alphabet.
The nondeterministic state complexity of <i>L</i>^<i>k</i>
is demonstrated to be <i>nk</i>.
This bound is shown to be tight over a two-letter alphabet.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tDoOk07a,
  title = {State Complexity of Power},
  author = {Domaratzki, Michael and Okhotin, Alexander},
  number = {845},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2008},
  keywords = {descriptional complexity, finite automata, state complexity, combined operations, concatenation},
  ISBN = {978-952-12-1964-1},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication