DROPS

Document

DOI: 10.4230/LIPIcs.LICS.2026.5

A Complexity Bound for Determinisation of Min-Plus Weighted Automata

Authors: Shaull Almagor, Guy Arbel, and Sarai Sheinvald

Published in: LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026)

Abstract

The determinisation problem for min-plus (tropical) weighted automata was recently shown to be decidable. However, the proof is purely existential, relying on several non-constructive arguments. Our contribution in this work is twofold: first, we present the first complexity bound for this problem, showing it is primitive recursive. Second, our techniques introduce a versatile framework to analyse runs of weighted automata in a constructive manner. In particular, this simplifies the previous decidability argument and provides a tighter analysis, thus serving as a critical step towards a tight complexity bound.

Cite as

Shaull Almagor, Guy Arbel, and Sarai Sheinvald. A Complexity Bound for Determinisation of Min-Plus Weighted Automata. In 41st Annual Symposium on Logic in Computer Science (LICS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 380, pp. 5:1-5:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{almagor_et_al:LIPIcs.LICS.2026.5,
  author =	{Almagor, Shaull and Arbel, Guy and Sheinvald, Sarai},
  title =	{{A Complexity Bound for Determinisation of Min-Plus Weighted Automata}},
  booktitle =	{41st Annual Symposium on Logic in Computer Science (LICS 2026)},
  pages =	{5:1--5:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-434-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{380},
  editor =	{Faggian, Claudia and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.LICS.2026.5},
  URN =		{urn:nbn:de:0030-drops-267925},
  doi =		{10.4230/LIPIcs.LICS.2026.5},
  annote =	{Keywords: Automata, Weighted Automata, Determinisation, Tropical, Min Plus, Primitive Recursive}
}

Document

Track B: Automata, Logic, Semantics, and Theory of Programming

DOI: 10.4230/LIPIcs.ICALP.2026.159

Unambiguisability and Register Minimisation of Min-Plus Models

Authors: Shaull Almagor, Guy Arbel, and Sarai Sheinvald

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

We study the unambiguisability problem for min-plus (tropical) weighted automata (WFAs), and the register-minimisation problem for tropical Cost Register Automata (CRAs), which are expressively-equivalent to WFAs. Both problems ask whether the “amount of nondeterminism’’ in the model can be reduced. We show that WFA unambiguisability is decidable for tropical WFAs. Our proof is via reduction to WFA determinisability, which was recently shown to be decidable. To obtain this reduction, we develop a characterisation of unambiguisability via gaps between runs. On the negative side, we show that CRA register minimisation is undecidable already for inputs with 7 registers, and hence also for any larger fixed number of registers.

Cite as

Shaull Almagor, Guy Arbel, and Sarai Sheinvald. Unambiguisability and Register Minimisation of Min-Plus Models. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 159:1-159:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{almagor_et_al:LIPIcs.ICALP.2026.159,
  author =	{Almagor, Shaull and Arbel, Guy and Sheinvald, Sarai},
  title =	{{Unambiguisability and Register Minimisation of Min-Plus Models}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{159:1--159:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.159},
  URN =		{urn:nbn:de:0030-drops-265479},
  doi =		{10.4230/LIPIcs.ICALP.2026.159},
  annote =	{Keywords: Automata, Weighted Automata, Determinisation, Unambiguous, Unambiguisation, Tropical, Min Plus}
}

Search Results

Documents authored by Sheinvald, Sarai

A Complexity Bound for Determinisation of Min-Plus Weighted Automata

Abstract

Cite as

Unambiguisability and Register Minimisation of Min-Plus Models

Abstract

Cite as

Thanks for your feedback!

Could not send message