The big-O problem for max-plus automata

Given two weighted automata A and B over the (N, max, plus) semi-ring we consider the problem of deciding whether there exists a constant c such that A(w) ≤ c B(w) + c for every word w. The problem is known as the big-O problem or affine domination. The problem is a relaxation of the containment problem; whether A(w) ≤ B(w) for all words w. Whilst the containment problem is undecidable, our results show that the big-O problem is decidable and PSPACE-complete.