Playing Pushdown Parity Games in a Hurry

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.

Provided by: Creative Commons Topic: Software Date Added: Oct 2012 Format: PDF

Find By Topic