Modal μ-calculus

In theoretical computer science, the modal μ-calculus (Lμ, Lμ, sometimes just μ-calculus, although this can have a more general meaning) is an extension of propositional modal logic (with many modalities) by adding the least fixed point operator μ and the greatest fixed point operator ν, thus a fixed-point logic. The (propositional, modal) μ-calculus originates with Dana Scott and Jaco de Bakker, and was further developed by Dexter Kozen into the version most used nowadays. It is used to describe properties of labelled transition systems and for verifying these properties. Many temporal logics can be encoded in the μ-calculus, including CTL* and its widely used fragments—linear temporal logic and computational tree logic. An algebraic view is to see it as an algebra of monotonic functions over a complete lattice, with operators consisting of functional composition plus the least and greatest fixed point operators; from this viewpoint, the modal μ-calculus is over the lattice of a power set algebra. The game semantics of μ-calculus is related to two-player games with perfect information, particularly infinite parity games. Let P (propositions) and A (actions) be two finite sets of symbols, and let Var be a countably infinite set of variables. The set of formulas of (propositional, modal) μ-calculus is defined as follows: each proposition and each variable is a formula; if and are formulas, then is a formula; if is a formula, then is a formula; if is a formula and is an action, then is a formula; (pronounced either: box or after necessarily ) if is a formula and a variable, then is a formula, provided that every free occurrence of in occurs positively, i.e. within the scope of an even number of negations. (The notions of free and bound variables are as usual, where is the only binding operator.) Given the above definitions, we can enrich the syntax with: meaning (pronounced either: diamond or after possibly ) meaning means , where means substituting for in all free occurrences of in .