@inproceedings{10.1007/11549345_43,
    Abstract = {We consider the complexity of infinite games played on finite graphs. We establish a framework in which the expressiveness and succinctness of different types of winning conditions can be compared. We show that the problem of deciding the winner in Muller games is PSPACE-complete. This is then used to establish PSPACE-completeness for Emerson-Lei games and for games described by Zielonka DAGs. Adaptations of the proof show PSPACE-completeness for the emptiness problem for Muller automata as well as the model-checking problem for such automata on regular trees. We also show co-NP-completeness for two classes of union-closed games: games specified by a basis and superset Muller games.},
    Address = {Berlin, Heidelberg},
    Author = {Hunter, Paul and Dawar, Anuj},
    BookTitle = {Mathematical Foundations of Computer Science 2005},
    Editor = {J{\c e}drzejowicz, Joanna and Szepietowski, Andrzej},
    File = {regularGames (0) - a - a - q.pdf},
    ISBN = {978-3-540-31867-5},
    Pages = {495--506},
    Publisher = {Springer Berlin Heidelberg},
    Title = {Complexity Bounds for Regular Games},
    Year = {2005},
    date-added = {2018-04-04 08:44:58 +0000},
    date-modified = {2018-04-04 08:44:58 +0000},
    doi = {10.1007/11549345_43}
}

@inproceedings{10.1007/11549345_43, Abstract = {We consider the complexity of infinite games played on finite graphs. We establish a framework in which the expressiveness and succinctness of different types of winning conditions can be compared. We show that the problem of deciding the winner in Muller games is PSPACE-complete. This is then used to establish PSPACE-completeness for Emerson-Lei games and for games described by Zielonka DAGs. Adaptations of the proof show PSPACE-completeness for the emptiness problem for Muller automata as well as the model-checking problem for such automata on regular trees. We also show co-NP-completeness for two classes of union-closed games: games specified by a basis and superset Muller games.}, Address = {Berlin, Heidelberg}, Author = {Hunter, Paul and Dawar, Anuj}, BookTitle = {Mathematical Foundations of Computer Science 2005}, Editor = {J{\c e}drzejowicz, Joanna and Szepietowski, Andrzej}, File = {regularGames (0) - a - a - q.pdf}, ISBN = {978-3-540-31867-5}, Pages = {495--506}, Publisher = {Springer Berlin Heidelberg}, Title = {Complexity Bounds for Regular Games}, Year = {2005}, date-added = {2018-04-04 08:44:58 +0000}, date-modified = {2018-04-04 08:44:58 +0000}, doi = {10.1007/11549345_43} }