THE BIG-O PROBLEM FOR MAX-PLUS AUTOMATA IS DECIDABLE (PSPACE-COMPLETE)

Daviaud, L ORCID: 0000-0002-9220-7118, Purser, D ORCID: 0000-0003-0394-1634 and Tcheng, M (2025) THE BIG-O PROBLEM FOR MAX-PLUS AUTOMATA IS DECIDABLE (PSPACE-COMPLETE) Logical Methods in Computer Science, 21 (3). pp. 3-35. ISSN 1860-5974, 1860-5974

Text Big-O-Journal-AAM.pdf - Author Accepted Manuscript Available under License Creative Commons Attribution. Download (634kB) | Preview

Abstract

We show that the big-O problem for max-plus automata, i.e. weighted automata over the semiring (N ∪{−∞}, 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.

Item Type:	Article
Uncontrolled Keywords:	Max-plus automata, Big-O, Decidability
Divisions:	Faculty of Science & Engineering Faculty of Science & Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	01 Jul 2025 08:17
Last Modified:	28 Feb 2026 15:05
DOI:	10.46298/lmcs-21(3:3)2025
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3193420
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.