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.

翻译：我们展示了 Max-Plus 自动机的大 O 问题是可判定的，并且是 PSPACE-完备的。大 O（或者说仿射占优问题）问题需要考虑，给定计算函数 f 和 g 的两个 Max-Plus 自动机，是否存在一个常数 c 使得 f < cg+ c。这个问题是在判定函数占优问题 f < g 的情况下的一种松弛形式，而这个问题是不可判定的。我们的可判定性结果使用了 Simon 的森林因子分解定理，并依赖于在一个有两个特殊运算（稳定和平坦化）下闭合的有限半群中检测特殊元素，这些元素我们称之为“见证人”。