Playing Pushdown Parity Games in a Hurry

Free registration required

Executive Summary

The authors continue the investigation of finite-duration variants of infinite-duration games by extending known results for games played on finite graphs to those played on infinite ones. In particular, they establish an equivalence between pushdown parity games and a finite-duration variant. This allows one to determine the winner of a pushdown parity game by solving a reachability game on a finite tree. Infinite two-player games on graphs are a powerful tool to model, verify, and synthesize open reactive systems and are closely related to fixed-point logics. The winner of a play in such a game typically emerges only after completing the whole (infinite) play.

  • Format: PDF
  • Size: 150.27 KB