2023/04/11 by Laure Daviaud, Daviaud, Laure, David Purser +2 · 1 citation
Computer Science · Mathematics · #Algorithm #Automaton #Combinatorics #Computational complexity theory #Computer science #Constant (computer programming) #Decidability #Discrete mathematics #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Logic in Computer Science (cs.LO) #Mathematics #PSPACE #Rewriting #Security and Verification in Computing #Semigroup #Theoretical computer science #Undecidable problem #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2304.05229
openalex publication_date 2023/04/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.