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.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers2
Builds on1
Related papers
- Algebraic Closure of Matrix Sets Recognized by 1-VASSRida Ait El Manssour, Mahsa Naraghi, Mahsa Shirmohammadi, James WorrellSODA 2026 · 1 citation
- Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted AutomataIsmaël Jecker, Filip Mazowiecki, David PurserLICS 2024 · 4 citations
- Quantifier Elimination for Regular Integer Linear-Exponential ProgrammingMikhail R. StarchakLICS 2025
- Ramsey Quantifiers over Automatic Structures: Complexity and Applications to VerificationPascal Bergsträßer, Moses Ganardi, Anthony W. Lin, Georg ZetzscheLICS 2022 · 3 citations
- Computing the linear hull: Deciding Deterministic? and Unambiguous? for weighted automata over fieldsJason P. Bell, Daniel SmertnigLICS 2023 · 6 citations
