Game Logic is Strong Enough for Parity Games

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

Abstract

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.

Links

PhilArchive



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

External links

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

Through your library

Similar books and articles

Logic games are complete for game logics.Johan van Benthem - 2003 - Studia Logica 75 (2):183-203.
Game Logic - An Overview.Marc Pauly & Rohit Parikh - 2003 - Studia Logica 75 (2):165-182.
Representation of Game Algebras.Yde Venema - 2003 - Studia Logica 75 (2):239-256.
The Basic Algebra of Game Equivalences.Valentin Goranko - 2003 - Studia Logica 75 (2):221-238.
Representation of game algebras.Yde Venema - 2003 - Studia Logica 75 (2):239 - 256.

Analytics

Added to PP
2016-02-14

Downloads
15 (#949,647)

6 months
4 (#795,160)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Neighborhood Semantics for Modal Logic.Eric Pacuit - 2017 - Cham, Switzerland: Springer.
The variable hierarchy for the games μ-calculus.Walid Belkhir & Luigi Santocanale - 2010 - Annals of Pure and Applied Logic 161 (5):690-707.
On guarded transformation in the modal -calculus.F. Bruse, O. Friedmann & M. Lange - 2015 - Logic Journal of the IGPL 23 (2):194-216.
Deciding the unguarded modal -calculus.Oliver Friedmann & Martin Lange - 2013 - Journal of Applied Non-Classical Logics 23 (4):353-371.

Add more citations

References found in this work

No references found.

Add more references