An Analysis of On-the-fly Determinization of Finite-state Automata
Ivan Baburin Ryan Cotterell
In this paper we establish an abstraction of on-the-fly determinization of
finite-state automata using transition monoids and demonstrate how it can be
applied to bound the asymptotics. We present algebraic and combinatorial
properties that are sufficient for a polynomial state complexity of the
deterministic automaton constructed on-the-fly. A special case of our findings
is that automata with many non-deterministic transitions almost always admit a
determinization of polynomial complexity. Furthermore, we extend our ideas to
weighted finite-state automata.