Lune

LICS2023Top-tier venue

The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete)

Laure Daviaud, David Purser

Abstract

We show that the big-O problem for max-plus automata, i.e. weighted automata over the semiring (ℕ ∪ –∞, max, +), is decidable and PSPACE-complete. The big-O (or affine domination) problem asks whether, given two max-plus automata computing functions f and g, there exists a constant c such that f ≤ cg + c. This is a relaxation of the containment problem asking whether f ≤ g, which is undecidable. Our decidability result uses Simon’s forest factorisation theorem, and relies on detecting specific elements, that we call witnesses, in a finite semigroup closed under two special operations: stabilisation and flattening.

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.

2 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • A Complexity Bound for Determinisation of Min-Plus Weighted Automata cites Determinization of Min-Plus Weighted Automata is Decidable
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers2

  1. Determinization of Min-Plus Weighted Automata is DecidableShaull Almagor, Guy Arbel, Sarai SheinvaldSODA 2026 · 1 citation
  2. A Complexity Bound for Determinisation of Min-Plus Weighted AutomataShaull Almagor, Guy Arbel, Sarai SheinvaldLICS 2026

Builds on1

  1. The boundedness and zero isolation problems for weighted automata over nonnegative rationalsWojciech Czerwinski, Engel Lefaucheux, Filip Mazowiecki, David Purser et al.LICS 2022 · 3 citations

Related papers

  1. Algebraic Closure of Matrix Sets Recognized by 1-VASSRida Ait El Manssour, Mahsa Naraghi, Mahsa Shirmohammadi, James WorrellSODA 2026 · 1 citation
  2. Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted AutomataIsmaël Jecker, Filip Mazowiecki, David PurserLICS 2024 · 4 citations
  3. Quantifier Elimination for Regular Integer Linear-Exponential ProgrammingMikhail R. StarchakLICS 2025
  4. Ramsey Quantifiers over Automatic Structures: Complexity and Applications to VerificationPascal Bergsträßer, Moses Ganardi, Anthony W. Lin, Georg ZetzscheLICS 2022 · 3 citations
  5. Computing the linear hull: Deciding Deterministic? and Unambiguous? for weighted automata over fieldsJason P. Bell, Daniel SmertnigLICS 2023 · 6 citations
Dusk over the sea between two cliffs drawn in fine vertical lines