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

Ivan Baburin, Ryan Cotterell
8/27/2023
cs.FLcs.CL

No confident code implementation found for this paper.

Abstract

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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

On-the-fly Synthesis for LTL over Finite Traces: An Efficient Approach that Counts

81% match2024

Unambiguity and Fewness for Nonuniform Families of Polynomial-Size Nondeterministic Finite Automata

80% match2023

Neural Networks as Universal Finite-State Machines: A Constructive Deterministic Finite Automaton Theory

78% match2025

Algorithms for Acyclic Weighted Finite-State Automata with Failure Arcs

77% match1 repo52023

Active Learning of Symbolic Automata Over Rational Numbers

77% match2025

Computational Dynamical Systems

76% match2024

Cite this paper

@article{baburin2023analysis,
  title  = {An Analysis of On-the-fly Determinization of Finite-state Automata},
  author = {Ivan Baburin and Ryan Cotterell},
  year   = {2023},
  eprint = {2308.14077},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2308.14077v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2308.14077.svg)](https://codeofpaper.com/paper/2308.14077)

Discussion