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

Tools

Daviaud, Laure, Purser, David and Tcheng, Marie (2025) The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete). Logical Methods in Computer Science. ISSN 1860-5974 (In Press)

[thumbnail of 2304.05229v3] PDF (2304.05229v3) - Accepted Version
Restricted to Repository staff only until 31 December 2099.
Request a copy

Abstract

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 < 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: 4* ,/dk/atira/pure/researchoutput/REFrank/4_
Faculty \ School: Faculty of Science > School of Computing Sciences
Related URLs:
Depositing User: LivePure Connector
Date Deposited: 24 Apr 2025 09:32
Last Modified: 24 Apr 2025 09:32
URI: https://ueaeprints.uea.ac.uk/id/eprint/99069
DOI: issn:1860-5974

Actions (login required)

View Item View Item