8 - The Modal Mu-Calculus
from PART II - LOGICS
Published online by Cambridge University Press: 13 October 2016
Summary
We have noted that the basic modal logic BML suffers from the deficiency of not being able to make assertions about connectivity, i.e. every BML formula can only ‘look’ up to a certain depth into a transition system. This is of course not enough for many purposes, and this is why richer formalisms like reachability logic TLR and the computation tree logic CTL have been introduced. As we demonstrated in Chapter 7, these logics possess temporal operatorswhich directly translate such assertions into the syntax of a logic. As we showed in Section 7.1.5, all temporal operators in CTL added on top of BML have simple and elegant characterisations in terms of least or greatest fixpoint solutions to certain equations.
The modal μ-calculus Lμ uses this idea as a general principle in order to add expressive power to the basic modal logic BML. It only features two additional syntactic constructs: a least and a greatest fixpoint operator. Thus, it differs from the other logics studied here in the way that the fixpoint character of a formula is being made explicit in it. This has pros and cons: it allows any least or greatest fixpoint solution of an equation expressed with basic modal logic to be defined; on the other hand this results in a far less intuitive syntax of the logic when compared to the other temporal logics.
These two aspects determine the role that the modal μ-calculus plays in the world of temporal logics. The generic use of fixpoint quantifiers gives it a relatively high expressive power. Many other temporal logics can be embedded into themodal μ-calculus. The explicit use of fixpoint quantifiers come with a generic instruction for doing model checking using fixpoint iteration. Such algorithms can then be specialised to the embedded temporal logics. Thus, the modal μ-calculus is often called the backbone of temporal logics.
Structure of the chapter. In Section 8.1 we start by introducing the concept of fixpoint quantification which leads to the formal logic called the modal μ-calculus. Early on we show that it can embed CTL simply because this translation is helpful in understanding the use of fixpoint quantifiers for the specification of temporal behaviour.
- Type
- Chapter
- Information
- Temporal Logics in Computer ScienceFinite-State Systems, pp. 271 - 328Publisher: Cambridge University PressPrint publication year: 2016