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

Daviaud, Laure and Purser, David (2023) The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete). In: 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). Proceedings - Symposium on Logic in Computer Science . The Institute of Electrical and Electronics Engineers (IEEE). ISBN 9798350335873

PDF (BigOProblemMaxPlusAutomataIsDecidable) - 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, 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.

Item Type:	Book Section
Additional Information:	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.
Uncontrolled Keywords:	software,mathematics(all),4* ,/dk/atira/pure/subjectarea/asjc/1700/1712
Faculty \ School:	Faculty of Science > School of Computing Sciences
Related URLs:	http://www.scopus.com/inward/record.url?... https://arxiv.org/abs/2304.05229
Depositing User:	LivePure Connector
Date Deposited:	14 Jun 2023 14:26
Last Modified:	31 Oct 2023 02:48
URI:	https://ueaeprints.uea.ac.uk/id/eprint/92392
DOI:	10.1109/LICS56636.2023.10175798

Actions (login required)

View Item