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

Laure Daviaud; David Purser; Marie Tcheng

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

Laure Daviaud, David Purser, Marie Tcheng

School of Computing Sciences

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Journal	Logical Methods in Computer Science
Publication status	Accepted/In press - 21 Mar 2025

Access to Document

https://arxiv.org/abs/2304.05229Licence: CC BY

Embargoed Document

2304.05229v3
Accepted author manuscript, 609 KB
Embargo ends: 31/12/99

Cite this

@article{fe3bb454cdb64077bcb2471083740c32,

title = "The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete)",

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. ",

author = "Laure Daviaud and David Purser and Marie Tcheng",

year = "2025",

month = mar,

day = "21",

language = "English",

journal = "Logical Methods in Computer Science",

issn = "1860-5974",

publisher = "Technischen Universitat Braunschweig",

}

TY - JOUR

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

AU - Daviaud, Laure

AU - Purser, David

AU - Tcheng, Marie

PY - 2025/3/21

Y1 - 2025/3/21

N2 - 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.

AB - 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.

M3 - Article

SN - 1860-5974

JO - Logical Methods in Computer Science

JF - Logical Methods in Computer Science

ER -