Showing cs.FLShow all
3 papers · 1 filter
cs.FL2026
A Complexity Bound for Determinisation of Min-Plus Weighted Automata
Shaull Almagor, Guy Arbel, Sarai Sheinvald
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-construct…
cs.FL2026
Unambiguisability and Register Minimisation of Min-Plus Models
Shaull Almagor, Guy Arbel, Sarai Sheinvald
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…
cs.FL2025
Determinization of Min-Plus Weighted Automata is Decidable
Shaull Almagor, Guy Arbel, Sarai Sheinvald
We show that the determinization problem for min-plus (tropical) weighted automata is decidable, thus resolving this long-standing open problem. In doing so, we develop a new toolb…