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

arXiv: https://arxiv.org/abs/2308.14077 · HTML: https://mlsanity.com/paper/2308.14077/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 19 references that are in the map.
- First posted on arXiv 27 Aug 2023.

## Builds on (most cited first, 1 of 1)

- [Maximum Flow and Minimum-Cost Flow in Almost-Linear Time](https://mlsanity.com/paper/2203.00671/) (2022)

## Abstract (arXiv)

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.