Automata on one symbol
J. Dénes, K. H. Kim, F.W. Roush · Birkhäuser Basel eBooks · 1983
We obtain bounds on the number of states of a one symbol deterministic automaton needed for the automaton to be equivalent to an arbitrary nondeterministic automaton on n states. We conjecture that they are best possible.