TY - GEN
T1 - The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete)
AU - Daviaud, Laure
AU - Purser, David
N1 - Funding Information: The first author has been supported for this work by the EPSRC grant EP/T018313/1. The second author was partially supported by the ERC grant INFSYS, agreement no. 950398.
PY - 2023/7/14
Y1 - 2023/7/14
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85165956224&partnerID=8YFLogxK
U2 - 10.1109/LICS56636.2023.10175798
DO - 10.1109/LICS56636.2023.10175798
M3 - Conference contribution
T3 - Proceedings - Symposium on Logic in Computer Science
BT - 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
PB - The Institute of Electrical and Electronics Engineers (IEEE)
ER -