Streett Games on Finite Graphs

Florian Horn

LIAFA, University of Paris


Streett games are an adequate model of strong fairness in reactive systems. We present here a family of games where winning strategies require memory factorial in the size of the Streett condition, and a new algorithm for Streett games of complexity $n^k.k!$, thus better than the LAR reduction to parity games and the algorithm of (Jurdzinski, 2000). Last updated: May 23, 2005