An Analysis of On-the-fly Determinization of Finite-state Automata
This work addresses a theoretical bottleneck in automata theory for researchers, providing incremental algebraic insights into determinization complexity.
The paper tackles the problem of on-the-fly determinization of finite-state automata by establishing an abstraction using transition monoids to bound asymptotics, showing that automata with many non-deterministic transitions often have polynomial complexity determinization, and extends this to weighted automata.
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.