State complexity
State complexity is an area of theoretical computer science
dealing with the size of abstract automata,
such as different kinds of finite automata.
The classical result in the area is that
simulating an -state
nondeterministic finite automaton
by a deterministic finite automaton
requires exactly states in the worst case.
Transformation between variants of finite automata
Finite automata can bedeterministic and
nondeterministic,
one-way
and two-way
.
Other related classes are
unambiguous,
self-verifying
and alternating finite automata.
These automata can also be two-way.
All these machines can accept exactly the regular languages.
However, the size of different types of automata
necessary to accept the same language
may be different.
For any two types of finite automata,
the state complexity tradeoff between them
is an integer function
where is the least number of states in automata of the second type
sufficient to recognize every language
recognized by an -state automaton of the first type.
The following results are known.
- NFA to DFA: states. This is the subset construction by Rabin and Scott, proved optimal by Lupanov.
- UFA to DFA: states, see Leung, An earlier lower bound by Schmidt was smaller.
- NFA to UFA: states, see Leung. There was an earlier smaller lower bound by Schmidt.
- SVFA to DFA: states, see Jirásková and Pighizzini
- 2DFA to DFA: states, see Kapoutsis. Earlier construction by Shepherdson used more states, and an earlier lower bound by Moore was smaller.
- 2DFA to NFA:, see Kapoutsis. Earlier construction by Birget used more states.
- 2NFA to NFA:, see Kapoutsis.
- * 2NFA to NFA accepting the complement: states, see Vardi.
- AFA to DFA: states, see Chandra, Kozen and Stockmeyer.
- AFA to NFA: states, see Fellah, Jürgensen and Yu.
- 2AFA to DFA:, see Ladner, Lipton and Stockmeyer.
- 2AFA to NFA:, see Geffert and Okhotin.
The 2DFA vs. 2NFA problem and logarithmic space
with polynomially many states, i.e. whether there is a polynomial
such that for every -state 2NFA
there exists a -state 2DFA.
The problem was raised by Sakoda and Sipser,
who compared it to the P vs. NP problem
in the computational complexity theory.
Berman and Lingas discovered a formal relation between this problem
and the L vs. NL open problem.
This relation was further elaborated by Kapoutsis.
State complexity of operations for finite automata
Given a binary regularity-preserving operation on languagesand a family of automata X,
the state complexity of
is an integer function such that
- for each m-state X-automaton A and n-state X-automaton B there is an -state X-automaton for, and
- for all integers m, n there is an m-state X-automaton A and an n-state X-automaton B such that every X-automaton for must have at least states.
The first results on state complexity of operations for DFAs
were published by Maslov
and by Yu, Zhuang and Salomaa.
Holzer and Kutrib
pioneered the state complexity of operations on NFA.
The known results for basic operations are listed below.
Union
If language requires m statesand language requires n states,
how many states requires?
- DFA: states, see Maslov and Yu, Zhuang and Salomaa.
- NFA: states, see Holzer and Kutrib.
- UFA: between and states, see Jirásek, Jirásková and Šebej.
- SVFA: states, see Jirásek, Jirásková and Szabari.
- 2DFA: between and states, see Kunc and Okhotin.
- 2NFA: states, see Kunc and Okhotin.
Intersection
- DFA: states, see Maslov and Yu, Zhuang and Salomaa.
- NFA: states, see Holzer and Kutrib.
- UFA: states, see Jirásek, Jirásková and Šebej.
- SVFA: states, see Jirásek, Jirásková and Szabari.
- 2DFA: between and states, see Kunc and Okhotin.
- 2NFA: between and states, see Kunc and Okhotin.
Complementation
then how many states its complement requires?
- DFA: states, by exchanging accepting and rejecting states.
- NFA: states, see Birget.
- UFA: at least and at most states, see Okhotin for the lower bound and Jirásek, Jirásková and Šebej for the upper bound. Raskin recently proved a superpolynomial lower bound.
- SVFA: states, by exchanging accepting and rejecting states.
- 2DFA: at least and at most states, see Geffert, Mereghetti and Pighizzini.
Concatenation
- DFA: states, see Maslov and Yu, Zhuang and Salomaa.
- NFA: states, see Holzer and Kutrib.
- UFA: states, see Jirásek, Jirásková and Šebej.
- SVFA: states, see Jirásek, Jirásková and Szabari.
- 2DFA: at least and at most states, see Jirásková and Okhotin.
Kleene star
- DFA: states, see Maslov and Yu, Zhuang and Salomaa.
- NFA: states, see Holzer and Kutrib.
- UFA: states, see Jirásek, Jirásková and Šebej.
- SVFA: states, see Jirásek, Jirásková and Szabari.
- 2DFA: at least and at most states, see Jirásková and Okhotin.
Reversal
- DFA: states, see Mirkin, Leiss, and Yu, Zhuang and Salomaa.
- NFA: states, see Holzer and Kutrib.
- UFA: states.
- SVFA: states, see Jirásek, Jirásková and Szabari.
- 2DFA: between and states, see Jirásková and Okhotin.
Finite automata over a unary alphabet
Let be Landau's function.
Transformation between models
For a one-letter alphabet, transformations between different types of finite automata are sometimes more efficient than in the general case.- NFA to DFA: states, see Chrobak.
- 2DFA to DFA: states, see Chrobak and Kunc and Okhotin.
- 2NFA to DFA: states, see Mereghetti and Pighizzini. and Geffert, Mereghetti and Pighizzini.
- NFA to 2DFA: at most states, see Chrobak.
- 2NFA to 2DFA: at most states, proved by implementing the method of Savitch's theorem, see Geffert, Mereghetti and Pighizzini.
- UFA to DFA:, see Okhotin.
- NFA to UFA:, see Okhotin.
Union
- DFA: states, see Yu, Zhuang and Salomaa.
- NFA: states, see Holzer and Kutrib.
- 2DFA: between and states, see Kunc and Okhotin.
- 2NFA: states, see Kunc and Okhotin.
Intersection
- DFA: states, see Yu, Zhuang and Salomaa.
- NFA: states, see Holzer and Kutrib.
- 2DFA: between and states, see Kunc and Okhotin.
- 2NFA: between and states, see Kunc and Okhotin.
Complementation
- DFA: states.
- NFA: states, Holzer and Kutrib.
- UFA: at least and at most states, see Okhotin.
- 2DFA: at least and at most states, see Kunc and Okhotin.
- 2NFA: at least and at most states. The upper bound is by implementing the method of the Immerman–Szelepcsényi theorem, see Geffert, Mereghetti and Pighizzini.
Concatenation
- DFA: states, see Yu, Zhuang and Salomaa.
- NFA: between and states, see Holzer and Kutrib.
- 2DFA: states, see Kunc and Okhotin.
- 2NFA: states, see Kunc and Okhotin.
Kleene star
- DFA: states, see Yu, Zhuang and Salomaa.
- NFA: states, see Holzer and Kutrib.
- UFA: states, see Okhotin.
- 2DFA: states, see Kunc and Okhotin.
- 2NFA: states, see Kunc and Okhotin.