The big-O problem for max-plus automata

Prelegent(ci)

David Purser

Afiliacja

MIM UW

Termin

30 listopada 2022 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

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.

---