Attractor decompositions and their applications in games and automata

Prelegent(ci)

Marcin Jurdziński

Afiliacja

University of Warwick

Termin

23 marca 2022 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

An attractor decomposition is a natural inductively defined decomposition of a graph that satisfies the parity condition, and its “shape” can be described by an ordered tree. The McNaughton-Zielonka algorithm implicitly produces an attractor decomposition of the winning set in a parity game. We argue that attractor decompositions and their trees can be used to measure the structural complexity of a winning strategy. We illustrate this on two examples: relating Lehtinen’s register number of a parity game to the smallest Strahler number of its attractor decomposition tree, and a quasi-polynomial translation from alternating parity automata on words to alternating weak automata.

---