Multi-valued model checking games

摘要

This work extends the game-based framework of μ-calculus model checking to the multi-valued setting. In multi-valued model checking a formula is interpreted over a Kripke structure defined over a lattice. The value of the formula is also an element of the lattice. This problem has many applications in verification, such as handling abstract or partial models, analyzing systems in the presence of inconsistent views, and performing temporal logic query checking. We define a new game for the multi-valued model checking problem of the full μ-calculus, and demonstrate how to derive from it a direct model checking algorithm for its alternation-free fragment. The algorithm handles the multi-valued structure without any reduction. We investigate the properties of the new game, both independently, and in comparison to the automata-based approach. We show that the usual resemblance between the automata-based and the game-based approach does not hold in the multi-valued setting and show how it can be regained by changing the nature of the game.