Streett Games on Finite Graphs
Florian Horn · 2005
Abstract. Streett Games are an adequate model of strong fairness in reactive systems. We show that solving these games is co-NP complete, and that they require memory factorial in the size of the winning con-dition, even when the size of the game is polynomial. Two algorithms, computing the strategies of both players, are also presented. 1