Game logic is strong enough for parity games

Studia Logica 75 (2):205 - 219 (2003)
  Copy   BIBTEX


We investigate the expressive power of Parikh's Game Logic interpreted in Kripke structures, and show that the syntactical alternation hierarchy of this logic is strict. This is done by encoding the winning condition for parity games of rank n. It follows that Game Logic is not captured by any finite level of the modal -calculus alternation hierarchy. Moreover, we can conclude that model checking for the -calculus is efficiently solvable iff this is possible for Game Logic.



    Upload a copy of this work     Papers currently archived: 92,369

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library


Added to PP

71 (#232,838)

6 months
14 (#186,781)

Historical graph of downloads
How can I increase my downloads?

References found in this work

No references found.

Add more references