Formula size games for modal logic and $\mu$-calculus

Abstract

We propose a new version of formula size game for modal logic. The game characterizes the equivalence of pointed Kripke-models up to formulas of given numbers of modal operators and binary connectives. Our game is similar to the well-known Adler-Immerman game. However, due to a crucial difference in the definition of positions of the game, its winning condition is simpler, and the second player does not have a trivial optimal strategy. Thus, unlike the Adler-Immerman game, our game is a genuine two-person game. We illustrate the use of the game by proving a non-elementary succinctness gap between bisimulation invariant first-order logic $\mathrm{FO}$ and (basic) modal logic $\mathrm{ML}$. We also present a version of the game for the modal $\mu$-calculus ${\mathrm{L}}_{\mu }$ and show that $\mathrm{FO}$ is also non-elementarily more succinct than ${\mathrm{L}}_{\mu }$.

This is a preprint of an article published in Journal of Logic and Computation Published by Oxford University Press. arXiv admin note: substantial text overlap with arXiv:1604.07225

References in corpus (1)

• Succinctness in subsystems of the spatial mu-calculus

Cited by in corpus (1)

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