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 formula_1-state
nondeterministic finite automaton
by a deterministic finite automaton
requires exactly formula_2 states in the worst case.
Transformation between variants of finite automata.
Finite automata can be
deterministic and
nondeterministic,
one-way (DFA, NFA)
and two-way
(2DFA, 2NFA).
Other related classes are
unambiguous (UFA),
self-verifying (SVFA)
and alternating (AFA) finite automata.
These automata can also be two-way (2UFA, 2SVFA, 2AFA).
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 formula_3
where formula_4 is the least number of states in automata of the second type
sufficient to recognize every language
recognized by an formula_1-state automaton of the first type.
The following results are known.
The 2DFA vs. 2NFA problem and logarithmic space.
It is an open problem whether all 2NFAs can be converted to 2DFAs
with polynomially many states, i.e. whether there is a polynomial formula_18
such that for every formula_1-state 2NFA
there exists a formula_18-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 languages formula_21
and a family of automata X (DFA, NFA, etc.),
the state complexity of formula_21
is an integer function formula_23 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
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 formula_28 requires m states
and language formula_29 requires n states,
how many states formula_30 requires?
Intersection.
How many states formula_39 requires?
Complementation.
If language L requires n states
then how many states its "complement" requires?
Concatenation.
How many states formula_55 requires?
Finite automata over a unary alphabet.
State complexity of finite automata with a one-letter ("unary") alphabet, pioneered by Chrobak, is different from the multi-letter case.
Let formula_74 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.
Further reading.
Surveys of state complexity
were written by Holzer and Kutrib
and by Gao et al.
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.