2026-09-08T02:21:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26547 2026-09-05T19:47:14Z ddc:004 open_access

Unambiguisability and Register Minimisation of Min-Plus Models Almagor, Shaull Arbel, Guy Sheinvald, Sarai Automata Weighted Automata Determinisation Unambiguous Unambiguisation Tropical Min Plus 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shaull Almagor and Guy Arbel and Sarai Sheinvald 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.159 urn:nbn:de:0030-drops-265479 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.159 eng https://creativecommons.org/licenses/by/4.0/legalcode