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 .

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (4)

Related concepts (3)

Related courses (2)

Related lectures (8)

AR-365: Theory and architectural culture

Le cours offre un résumé de la théorie et la culture architecturales depuis 1789 dans le monde occidentale. Le but est de comprendre des textes dans lesquels l'architecture est définie comme une disci

AR-366: Theory and architectural culture: exercises

Le cours offre une méthode pour discerner et comprendre les idées, les théories et les valeurs culturelles dans des bâtiments et des projets d'architecture.

Kripke structure (model checking)

This article describes Kripke structures as used in model checking. For a more general description, see Kripke semantics. A Kripke structure is a variation of the transition system, originally proposed by Saul Kripke, used in model checking to represent the behavior of a system. It consists of a graph whose nodes represent the reachable states of the system and whose edges represent state transitions, together with a labelling function which maps each node to a set of properties that hold in the corresponding state.

Linear temporal logic

In logic, linear temporal logic or linear-time temporal logic (LTL) is a modal temporal logic with modalities referring to time. In LTL, one can encode formulae about the future of paths, e.g., a condition will eventually be true, a condition will be true until another fact becomes true, etc. It is a fragment of the more complex CTL*, which additionally allows branching time and quantifiers. LTL is sometimes called propositional temporal logic, abbreviated PTL.

Temporal logic

In logic, temporal logic is any system of rules and symbolism for representing, and reasoning about, propositions qualified in terms of time (for example, "I am always hungry", "I will eventually be hungry", or "I will be hungry until I eat something"). It is sometimes also used to refer to tense logic, a modal logic-based system of temporal logic introduced by Arthur Prior in the late 1950s, with important contributions by Hans Kamp. It has been further developed by computer scientists, notably Amir Pnueli, and logicians.

Temporal analysis of multimodal data to predict collaborative learning outcomes

Kshitij Sharma, Jennifer Kaitlyn Olsen

The analysis of multiple data streams is a long-standing practice within educational research. Both multimodal data analysis and temporal analysis have been applied successfully, but in the area of collaborative learning, very few studies have investigated ...

WILEY2020

Robust Control Policies Given Formal Specifications in Uncertain Environments

Maryam Kamgarpour, Tony Alan Wood

We consider robust control synthesis for linear systems with complex specifications that are affected by uncertain disturbances. This letter is motivated by autonomous systems interacting with partially known, time-varying environments. Given a specificati ...

2017

From Liveness to Promptness

Liveness temporal properties state that something

good'' eventually happens, e.g., every request is eventually granted. In Linear Temporal Logic (LTL), there is no a priori bound on the

wait time'' for an eventually to be fulfilled. That is,

F\theta

...

2007

Modal and Tonal Music

Explores modal and tonal music, analyzing popular music examples like the Beatles' 'Norwegian Wood' to understand scales, tonics, and modes.

Architecture and Society: Innovations, Critique, and Resistance AR-365: Theory and architectural culture

Explores the role of architecture and architects in modern society, questioning if architects can shape society or if architecture is determined by social, political, and economic conditions.

Solving Parity Games in Practice

Explores practical aspects of solving parity games, including winning strategies, algorithms, complexity, determinism, and heuristic approaches.