The big-O problem for max-plus automata

Speaker(s)

David Purser

Affiliation

MIM UW

Date

Nov. 30, 2022, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

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.

---