Daviaud, Laure, Purser, David 
ORCID: 0000-0003-0394-1634 and Tcheng, Marie
(2025)
The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete).
Logical Methods in Computer Science, Volume (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
<jats:p>We show that the big-O problem for max-plus automata 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 &lt; cg+ c. This is a relaxation of the containment problem asking whether f &lt; 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.</jats:p>
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | 46 Information and Computing Sciences |
| Divisions: | Faculty of Science and Engineering Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 01 Jul 2025 08:17 |
| Last Modified: | 15 Aug 2025 11:08 |
| DOI: | 10.46298/lmcs-21(3:3)2025 |
| Related Websites: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3193420 |
Altmetric
Altmetric