Bounded Game-Theoretic Semantics for Modal Mu-Calculus and Some Variants

Lauri Hella
Antti Kuusisto
Raine Rönnholm

We introduce a new game-theoretic semantics (GTS) for the modal mu-calculus. Our so-called bounded GTS replaces parity games with alternative evaluation games where only finite paths arise; infinite paths are not needed even when the considered transition system is infinite. The novel games offer alternative approaches to various constructions in the framework of the mu-calculus. For example, they have already been successfully used as a basis for an approach leading to a natural formula size game for the logic. While our main focus is introducing the new GTS, we also consider some applications to demonstrate its uses. For example, we consider a natural model transformation procedure that reduces model checking games to checking a single, fixed formula in the constructed models, and we also use the GTS to identify new alternative variants of the mu-calculus with PTime model checking.

In Jean-Francois Raskin and Davide Bresolin: Proceedings 11th International Symposium on Games, Automata, Logics, and Formal Verification (GandALF 2020), Brussels, Belgium, September 21-22, 2020, Electronic Proceedings in Theoretical Computer Science 326, pp. 82–96.
The official conference version of the extended preprint https://arxiv.org/abs/1706.00753.
Published: 20th September 2020.

ArXived at: https://dx.doi.org/10.4204/EPTCS.326.6 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org