A Complexity Bound for Determinisation of Min-Plus Weighted Automata

2026/02/01 by Shaull Almagor, Guy Arbel, Sarai Sheinvald · 1 voice
Computer Science · #cs.FL

paper · pdf · doi:10.48550/arxiv.2602.01221

arxiv published 2026/02/01 · arxiv updated 2026/05/05

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, placing it in the Fast-growing hierarchy. 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.

Citations

• The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete)
• Reachability in Vector Addition Systems is Ackermann-complete
• The Reachability Problem for Petri Nets is Not Primitive Recursive
• On Delay and Regret Determinization of Max-Plus Automata
• Trace Inclusion for One-Counter Nets Revisited
• Complexity Hierarchies Beyond Elementary
• Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton
• Compact Representations by Finite-State Transducers
• On the definition of a family of automata

Discussions

• Shaull Almagor, Guy Arbel, Sarai Sheinvald: A Complexity Bound for Determinisation of Min-Plus Weighted Automata https://arxiv.org/abs/2602.01221 https://arxiv.org/pdf/2602.01221 https://arxiv.org/htm [bsky, 0 points, 0 comments]

Related

• Determinization of Min-Plus Weighted Automata is Decidable
• Representing One Letter Weighted Automata Over the Tropical Semiring
• Unambiguisability and Register Minimisation of Min-Plus Models
• Notes on Equivalence and Minimization of Weighted Automata
• Bideterministic Weighted Automata