A Complexity Bound for Determinisation of Min-Plus Weighted Automata
For researchers in automata theory, this provides a critical step towards a tight complexity bound for a previously open problem.
The paper establishes the first complexity bound for determinisation of min-plus weighted automata, placing it in the Fast-growing hierarchy, and provides a constructive framework that simplifies the previous decidability argument.
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.