The bibliographic entry was discovered and compiled by a machine, and published without a person checking it against the publication. The publication itself is the authors' own work — this badge says nothing about it.

Faster Solutions of Rabin and Streett Games

The work

AuthorsNir Piterman; Amir Pnueli
Editors
Typemisc
Year2006
Citekeypiterman2006faster

Where it appeared

Published inProceedings - Symposium on Logic in Computer Science
PublisherInstitute of Electrical and Electronics Engineers
Pages275--284

Identifiers

DOI10.1109/lics.2006.23
OpenAlexW2098682681

Access

Landing pagehttps://doi.org/10.1109/lics.2006.23

From OpenAlex, which stores abstracts as an index of words and their positions: what is shown is rebuilt from that, and reads fluently whether or not it is what the author wrote.

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. By computing directly and explicitly the ranking we can solve such games in time O(mnk+1kk!) and space O(nk) for Rabin and O(nkk!) for Streett where n is the number of states, m the number of transitions, and k the number of pairs in the winning condition. In order to prove completeness of the ranking method we give a recursive fixpoint characterization of the winning regions in these games. We then show that by keeping intermediate values during the fixpoint evaluation, we can solve such games symbolically in time O(nk+1k!) and space O(nk+1k!). These results improve on the current bounds of O(mn2kk!) time in the case of direct (symbolic) solution or O(m(nk2k!)k) in the case of reduction to parity games

How it got here

How it got hereagent via openalex
Added2026-10-26 23:24 UTC
Not denied bya person 2026-10-29 17:12 UTC

Cite it as

@misc{piterman2006faster,
  title        = {Faster Solutions of Rabin and Streett Games},
  author       = {Nir Piterman and Amir Pnueli},
  year         = {2006},
  journal      = {Proceedings - Symposium on Logic in Computer Science},
  publisher    = {Institute of Electrical and Electronics Engineers},
  pages        = {275--284},
  doi          = {10.1109/lics.2006.23},
}

This record lives at https://refs.drheap.org/piterman2006faster/ and will keep doing so.