Unambiguisability and Register Minimisation of Min-Plus Models

2025/12/10 by Almagor, Shaull, Arbel, Guy, Sheinvald, Sarai
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.2512.09484

Abstract

We study the unambiguisability problem for min-plus (tropical) weighted automata (WFAs), and the counter-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, thus resolving this long-standing open problem. Our proof is via reduction to WFA determinisability, which was recently shown to be decidable. On the negative side, we show that CRA counter minimisation is undecidable, even for a fixed number of registers (specifically, already for 7 registers).

Citations

• Determinization of Min-Plus Weighted Automata is Decidable
• Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted Automata
• Minimizing Cost Register Automata over a Field
• Computing the linear hull: Deciding Deterministic? and Unambiguous? for weighted automata over fields
• Weak Cost Register Automata are Still Powerful
• On Delay and Regret Determinization of Max-Plus Automata
• Compact Representations by Finite-State Transducers

Related

• Determinization of Min-Plus Weighted Automata is Decidable
• Weak Cost Register Automata are Still Powerful
• Minimizing Cost Register Automata over a Field
• Minimisation of Deterministic Parity and Buchi Automata and Relative Minimisation of Deterministic Finite Automata
• On minimising automata with errors