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

Laure Daviaud, David Purser

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.
Original languageEnglish
Title of host publication38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
PublisherThe Institute of Electrical and Electronics Engineers (IEEE)
ISBN (Electronic)9798350335873
Publication statusPublished - 14 Jul 2023

Publication series

NameProceedings - Symposium on Logic in Computer Science
ISSN (Print)1043-6871

Cite this