TY - JOUR

T1 - State complexity of power

AU - Domaratzki, Michael

AU - Okhotin, Alexander

PY - 2009/5/28

Y1 - 2009/5/28

N2 - The number of states in a deterministic finite automaton (DFA) recognizing the language Lk, where L is regular language recognized by an n-state DFA, and k ≥ 2 is a constant, is shown to be at most n 2(k - 1) n and at least (n - k) 2(k - 1) (n - k) in the worst case, for every n > k and for every alphabet of at least six letters. Thus, the state complexity of Lk is Θ (n 2(k - 1) n). In the case k = 3 the corresponding state complexity function for L3 is determined as frac(6 n - 3, 8) 4n - (n - 1) 2n - n with the lower bound witnessed by automata over a four-letter alphabet. The nondeterministic state complexity of Lk is demonstrated to be n k. This bound is shown to be tight over a two-letter alphabet.

AB - The number of states in a deterministic finite automaton (DFA) recognizing the language Lk, where L is regular language recognized by an n-state DFA, and k ≥ 2 is a constant, is shown to be at most n 2(k - 1) n and at least (n - k) 2(k - 1) (n - k) in the worst case, for every n > k and for every alphabet of at least six letters. Thus, the state complexity of Lk is Θ (n 2(k - 1) n). In the case k = 3 the corresponding state complexity function for L3 is determined as frac(6 n - 3, 8) 4n - (n - 1) 2n - n with the lower bound witnessed by automata over a four-letter alphabet. The nondeterministic state complexity of Lk is demonstrated to be n k. This bound is shown to be tight over a two-letter alphabet.

KW - Combined operations

KW - Concatenation

KW - Descriptional complexity

KW - Finite automata

KW - Power

KW - State complexity

UR - http://www.scopus.com/inward/record.url?scp=67349247787&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2009.02.025

DO - 10.1016/j.tcs.2009.02.025

M3 - Article

AN - SCOPUS:67349247787

VL - 410

SP - 2377

EP - 2392

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 24-25

ER -