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
Finite automata can be deterministic and nondeterministic, one-way (DFA, NFA) and two-way
Other related classes are unambiguous (UFA), self-verifying (SVFA) and alternating (AFA) finite automata.
All these machines can accept exactly the regular languages.
However, the size of different types of automata necessary to accept the same language (measured in the number of their states) may be different.
For any two types of finite automata, the state complexity tradeoff between them is an integer function
is the least number of states in automata of the second type sufficient to recognize every language recognized by an
The problem was raised by Sakoda and Sipser,[15] who compared it to the P vs. NP problem in the computational complexity theory.
Berman and Lingas[16] discovered a formal relation between this problem and the L vs. NL open problem.
[17] Given a binary regularity-preserving operation on languages
and a family of automata X (DFA, NFA, etc.
such that Analogous definition applies for operations with any number of arguments.
The first results on state complexity of operations for DFAs were published by Maslov [18] and by Yu, Zhuang and Salomaa.
[19] Holzer and Kutrib [20] pioneered the state complexity of operations on NFA.
The known results for basic operations are listed below.
State complexity of finite automata with a one-letter (unary) alphabet, pioneered by Chrobak,[34] is different from the multi-letter case.
For a one-letter alphabet, transformations between different types of finite automata are sometimes more efficient than in the general case.
Surveys of state complexity were written by Holzer and Kutrib[40][41] and by Gao et al.[42] New research on state complexity is commonly presented at the annual workshops on Descriptional Complexity of Formal Systems (DCFS), at the Conference on Implementation and Application of Automata (CIAA), and at various conferences on theoretical computer science in general.