DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.121

A Simple Algorithmic Framework for Disambiguation of Finite Automata

Authors: Mauricio Cari, Martín Muñoz, and Cristian Riveros

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

We study the task of disambiguation of finite state automata, namely, converting an automaton into an equivalent, unambiguous one. We do this by developing a novel and simple algorithmic framework that generalizes the subset construction for determinization, and that satisfies some desirable properties: (1) it preserves the original automaton if it was already unambiguous, (2) it computes the successor states on-the-fly and (3) computes each new state in polynomial time - this last point is crucial as it guarantees that the running time is polynomial in the size of the output automaton. Then, we show how to apply this framework for partial disambiguation: by changing the criterion that builds the new states, we develop algorithms for different levels of ambiguity, namely, finitely ambiguous, and polynomially ambiguous automata. These algorithms also satisfy condition (1) for their respective levels, and also (2) and (3). Finally, we show that the disambiguation framework can easily be extended to other models of automata like weighted automata.

Cite as

Mauricio Cari, Martín Muñoz, and Cristian Riveros. A Simple Algorithmic Framework for Disambiguation of Finite Automata. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 121:1-121:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cari_et_al:LIPIcs.ESA.2026.121,
  author =	{Cari, Mauricio and Mu\~{n}oz, Mart{\'\i}n and Riveros, Cristian},
  title =	{{A Simple Algorithmic Framework for Disambiguation of Finite Automata}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{121:1--121:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.121},
  URN =		{urn:nbn:de:0030-drops-272573},
  doi =		{10.4230/LIPIcs.ESA.2026.121},
  annote =	{Keywords: Algorithmic automata theory, unambiguous automata models, degree of ambiguity, determinization, disambiguation, weighted automata}
}

Search Results

Documents authored by Cari, Mauricio

A Simple Algorithmic Framework for Disambiguation of Finite Automata

Abstract

Cite as

Thanks for your feedback!

Could not send message