Limits on state increase when changing nondeterministic to deterministic automata
On 2DFA simulation of 1NFA: A Quadratic Limitation to a New Lower-Bound Method
Formal Languages and Automata Theory
Summary
The paper looks at how complicated a machine must get when turning a type of computing machine that can guess (nondeterministic) into one that works in a fixed way (deterministic). The authors confirmed an earlier finding that in the worst case, the new machine must have about the square of the original machine’s number of parts. They also showed that their new method can’t prove any bigger jump than this. This means if you want to prove bigger jumps, a different approach will be needed.
What this means in practice
- •For compiler developers: Understand limits on how much more complex deterministic parsers can become when converted from nondeterministic models.
- •For hardware designers: Avoid expecting reductions better than quadratic in hardware models that simulate nondeterministic automata with deterministic ones.
A theory result. No direct application yet.
Authors
Kehinde Adeogun, Christos A. Kapoutsis
Abstract
A recent result by the present authors established a quadratic lower bound, in the worst case, for the increase in the number of states when a one-way nondeterministic finite automaton is converted to a two-way deterministic finite automaton. Although this simply matched a well-known pre-existing quadratic lower bound by Chrobak, it used a distinct proof method. We show that, much like Chrobak's, this new method is also unable to deliver any lower bound strictly greater than quadratic.