Paper: Faster Solutions of Street and Rabin Games (at LICS 2006)

Authors: Nir Piterman Amir Pnueli

Abstract

In this paper we improve the complexity of solving Rabin and Streett games to approximately the square root of previous bounds. We introduce direct Rabin and Streett ranking that are a sound and complete way to characterize the winning sets in the respective games.

BibTeX

  @InProceedings{PitermanPnueli-FasterSolutionsofSt,
    author = 	 {Nir Piterman and Amir Pnueli},
    title = 	 {Faster Solutions of Street and Rabin Games},
    booktitle =  {Proceedings of the Twenty-First Annual IEEE Symposium on Logic in Computer Science (LICS 2006)},
    year =	 {2006},
    month =	 {August}, 
    pages =      {275--284},
    location =   {Seattle, Washington, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }