On the State Complexity of k-Entry Deterministic Finite Automata
Markus Holzer, Kai Salomaa, Sheng Yü · Universitätsbibliothek Gießen · 2001
A $k$-entry deterministic finite automaton is a deterministic finite automaton (DFA) which has exactly $k$ initial states. We show tight upper bounds on the state complexity of these automata, proving that the transformation of a $k$-entry DFA to an equivalent ordinary DFA increases the number of states by a polynomial of degree $k$. This improves a result of Kappes [8] to the case of binary languages. For unary languages, i.e, languages over a single letter alphabet, we only have an upper bound, which is not known to be sharp. Finally, we investigate the complexity of the minimization problem for $k$-entry DFAs showing that it is PSpace-complete.