The big-O problem for max-plus automata is decidable (PSPACE-Complete)

Daviaud, Laure; Purser, David; Tcheng, Marie

doi:10.46298/lmcs-21(3:3)2025

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, 21 (3). 3:1–3-3:35. ISSN 1860-5974

Preview

PDF (2304.05229v3) - Accepted Version
Available under License Creative Commons Attribution.
Download (623kB) | Preview

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:	big-o,decidability,max-plus automata,theoretical computer science,computer science(all),4* ,/dk/atira/pure/subjectarea/asjc/2600/2614
Faculty \ School:	Faculty of Science > School of Computing Sciences
Related URLs:	http://www.scopus.com/inward/record.url?... https://arxiv.org/abs/2304.05229 https://livrepository.liverpool.ac.uk/id...
Depositing User:	LivePure Connector
Date Deposited:	24 Apr 2025 09:32
Last Modified:	30 Oct 2025 10:31
URI:	https://ueaeprints.uea.ac.uk/id/eprint/99069
DOI:	10.46298/lmcs-21(3:3)2025

Downloads

Downloads per month over past year

Actions (login required)

View Item