Paper: A Complexity Bound for Determinisation of Min-Plus Weighted Automata (at LICS 2026)

Authors: Shaull Almagor Guy Arbel Sarai Sheinvald

Open access: https://doi.org/10.4230/LIPIcs.LICS.2026.5

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, showing it is primitive recursive. 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.

BibTeX

  @InProceedings{AlmagorArbelSheinva-AComplexityBoundfor,
    author = 	 {Shaull Almagor and Guy Arbel and Sarai Sheinvald},
    title = 	 {A Complexity Bound for Determinisation of Min-Plus Weighted Automata},
    booktitle =  {Proceedings of the Forty-First Annual Symposium on Logic in Computer Science (LICS 2026)},
    year =	 {2026},
    month =	 {July}, 
    pages =      {5:1--5:22},
    location =   {Lisbon, Portugal}, 
    publisher =	 {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
    doi =        {10.4230/LIPIcs.LICS.2026.5}
  }