Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Game Logic is Strong Enough for Parity Games

Dietmar BerwangerContact Information

(1) Mathematical Foundations of Computer Science, RWTH Aachen, 52056 Aachen, Aachen, Germany

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 mgr-calculus alternation hierarchy. Moreover, we can conclude that model checking for the mgr-calculus is efficiently solvable iff this is possible for Game Logic

game logic - modal mu-calculus - expressive power - model checking


Contact InformationDietmar Berwanger
Email: berwanger@informatik.rwth-aachen.de
Fulltext Preview (Small, Large)
Image of the first page of the fulltext


Export this article
Export this article as RIS | Text
 
Remote Address: 38.107.191.115 • Server: MPWEB36
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)