State complexity

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 (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 f where f(n) is the least number of states in automata of the second type sufficient to recognize every language recognized by an n-state automaton of the first type. The following results are known. • NFA to DFA: 2^n states. This is the subset construction by Rabin and Scott, proved optimal by Lupanov. • UFA to DFA: 2^n states, see Leung, An earlier lower bound by Schmidt was smaller. • NFA to UFA: 2^n-1 states, see Leung. • 2DFA to DFA: n(n^n-(n-1)^n) states, see Kapoutsis. Earlier construction by Shepherdson used more states, and an earlier lower bound by Moore was smaller. • 2DFA to NFA: \binom{2n}{n+1} = O(\frac{4^n}{\sqrt{n}}), see Kapoutsis. used more states. • 2NFA to NFA: \binom{2n}{n+1}, see Kapoutsis. • AFA to DFA: 2^{2^n} states, see Chandra, Kozen and Stockmeyer. • AFA to NFA: 2^n states, see Fellah, Jürgensen and Yu. • 2AFA to DFA: 2^{n2^n}, see Ladner, Lipton and Stockmeyer. • 2AFA to NFA: 2^{\Theta(n \log n)}, see Geffert and Okhotin. The 2DFA vs. 2NFA problem and logarithmic space {{unsolved|computer science|Does every n-state 2NFA have an equivalent \operatorname{poly}(n)-state 2DFA?}} It is an open problem whether all 2NFAs can be converted to 2DFAs with polynomially many states, i.e. whether there is a polynomial p(n) such that for every n-state 2NFA there exists a p(n)-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 \circ and a family of automata X (DFA, NFA, etc.), the state complexity of \circ is an integer function f(m,n) such that • for each m-state X-automaton A and n-state X-automaton B there is an f(m,n)-state X-automaton for L(A) \circ L(B), 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 L(A) \circ L(B) must have at least f(m,n) states. 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 L_1 requires m states and language L_2 requires n states, how many states does L_1 \cup L_2 require? • DFA: mn states, see Maslov • SVFA: mn states, see Jirásek, Jirásková and Szabari. • 2DFA: between m+n and 4m+n+4 states, see Kunc and Okhotin. • 2NFA: m+n states, see Kunc and Okhotin. Intersection How many states does L_1 \cap L_2 require? • DFA: mn states, see Maslov or Jirásková • UFA: at least n^{\tilde{\Omega}(\log n)} states, see Göös, Kiefer and Yuan, (this follows an earlier bound by Raskin); and at most \sqrt{n+1} \cdot 2^{0.5n} states, see Indzhev and Kiefer. • SVFA: n states, by exchanging accepting and rejecting states. • 2DFA: at least n and at most 4n states, see Geffert, Mereghetti and Pighizzini. Concatenation How many states does L_1 L_2 = \{w_1 w_2 \mid w_1 \in L_1, w_2 \in L_2\} require? • DFA: m \cdot 2^n - 2^{n-1} states, see Maslov Kleene star • DFA: \frac{3}{4} 2^n states, see Maslov Leiss, and Yu, Zhuang and Salomaa. • NFA: n+1 states, see Holzer and Kutrib. • UFA: n states. • SVFA: 2n+1 states, see Jirásek, Jirásková and Szabari. • 2DFA: between n+1 and n+2 states, see Jirásková and Okhotin. ==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 g(n)=e^{\Theta(\sqrt{n \ln n})} 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: g(n)+O(n^2) states, see Chrobak. • 2NFA to DFA: O(g(n)) states, see Mereghetti and Pighizzini. and Geffert, Mereghetti and Pighizzini. • NFA to 2DFA: at most O(n^2) states, see Chrobak. • NFA to UFA: g(n)+O(n^2), see Okhotin. and at most e^{\Theta(\sqrt[3]{n (\ln n)^2})} states, see Okhotin. • 2DFA: at least n and at most 2n+3 states, see Kunc and Okhotin. • 2NFA: at least n and at most O(n^8) states. The upper bound is by implementing the method of the Immerman–Szelepcsényi theorem, see Geffert, Mereghetti and Pighizzini. Concatenation • DFA: mn states, see Yu, Zhuang and Salomaa. • NFA: between m+n-1 and m+n states, see Holzer and Kutrib. • 2DFA: e^{\Theta(\sqrt{(m+n)\log(m+n)})} states, see Kunc and Okhotin. • 2NFA: e^{\Theta(\sqrt{(m+n)\log(m+n)})} states, see Kunc and Okhotin. Kleene star • DFA: (n-1)^2+1 states, see Yu, Zhuang and Salomaa. • NFA: n+1 states, see Holzer and Kutrib. • UFA: (n-1)^2+1 states, see Okhotin. • 2DFA: \Theta((g(n))^2) states, see Kunc and Okhotin. • 2NFA: \Theta(g(n)) states, see Kunc and Okhotin. ==Further reading==