An Analysis of On-the-fly Determinization of Finite-state Automata

08/27/2023
by   Ivan Baburin, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset