STATE-COMPLEXITY OF FINITE-STATE DEVICES, STATE COMPRESSIBILITY AND INCOMPRESSIBILITY

We study how the number of states may change when we convert between different finite-state devices. The devices that we consider are finite automata that are one-way or two-way, deterministic or nondeterministic or alternating. We obtain several new simulation results (e.g., an n-state 2NFA can be simulated by a 1NFA with less-than-or-equal-to 8n + 2 states, and by a 1AFA with less-than-or-equal-to n2 states), and state-incompressibility results (e.g., in order to simulate an n-state 2DFA, a 1NFA needs greater-than-or-equal-to square-root 2n-2 states, and a 2AFA needs greater-than-or-equal-to c square-root n states for some constant c, in general).