Attractor decompositions and their applications in games and automata

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.