Attractor decompositions and their applications in games and automata

Speaker(s)

Marcin Jurdziński

Affiliation

University of Warwick

Date

March 23, 2022, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

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.

---