Attractor decompositions in games and automata

An attractor decomposition is a decomposition of a graph that satisfies the parity condition, and its “shape” can be described by an ordered tree. We argue that attractor decompositions and their trees can be used to measure the structural complexity of a winning strategy in a parity game. We illustrate this on two examples: relating Lehtinen’s register number of a parity game to the Strahler number of its attractor decomposition tree, and a quasi-polynomial translation from alternating parity automata on words to alternating weak automata. [Joint work with Laure Daviaud, Karoliina Lehtinen, and Thejaswini K.S.]