Lune

LICS2026Top-tier venue

A Complexity Bound for Determinisation of Min-Plus Weighted Automata

Shaull Almagor, Guy Arbel, Sarai Sheinvald

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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Determinization of Min-Plus Weighted Automata is Decidable cites The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete)
  • Reachability in Vector Addition Systems is Ackermann-complete cites The Reachability Problem for Petri Nets is Not Primitive Recursive
  • The Reachability Problem for Petri Nets is Not Primitive Recursive cites Reachability in Vector Addition Systems is Ackermann-complete
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on4

  1. Reachability in Vector Addition Systems is Ackermann-completeWojciech Czerwinski, Lukasz OrlikowskiFOCS 2021 · 69 citations
  2. The Reachability Problem for Petri Nets is Not Primitive RecursiveJérôme LerouxFOCS 2021 · 62 citations
  3. The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete)Laure Daviaud, David PurserLICS 2023 · 1 citation
  4. Determinization of Min-Plus Weighted Automata is DecidableShaull Almagor, Guy Arbel, Sarai SheinvaldSODA 2026 · 1 citation

Related papers

  1. Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted AutomataIsmaël Jecker, Filip Mazowiecki, David PurserLICS 2024 · 4 citations
  2. Computing the linear hull: Deciding Deterministic? and Unambiguous? for weighted automata over fieldsJason P. Bell, Daniel SmertnigLICS 2023 · 6 citations
  3. On Learning Polynomial Recursive ProgramsAlex Buna-Marginean, Vincent Cheval, Mahsa Shirmohammadi, James WorrellPOPL 2024 · 7 citations
  4. Orbit-Finite-Dimensional Vector Spaces and Weighted Register AutomataMikolaj Bojanczyk, Bartek Klin, Joshua MoermanLICS 2021 · 5 citations
  5. Operational Algorithmic Game SemanticsBenedict Bunting, Andrzej S. MurawskiLICS 2023 · 1 citation
Dusk over the sea between two cliffs drawn in fine vertical lines