Bisimulation, modal logic and model checking games
Christine Stirling · Logic Journal of IGPL · 1999
We give a very brief introduction to how concurrent systems can be modelled within process calculi, as terms of an algebraic language whose behaviours are described using transitions. Reasoning has centred on two kinds of questions. One is relationships between descriptions of concurrent systems. The other is appropriate logics for describing crucial properties of concurrent systems. Bisimulation equivalence is briefly described. It can also be characterised in terms of modal logic (Hennessy-Milner logic). However as a logic it is not very expressive. So we also describe modal mu-calculus which is a very expressive temporal logic. In the main part of the paper we show that property checking can be understood in terms of game playing. In the finite state case, games underpin efficient model checking algorithms. The games are also definable independently of property checking as graph games which can be reduced to other combinatorial games. Keywords:Bisimulation, modal logic, fixed point, games