Mu-calcul | EPFL Graph Search

Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

En logique mathématique et en informatique théorique, le mu-calcul (ou logique du mu-calcul modal) est l'extension de la logique modale classique avec des opérateurs de points fixes. Selon Bradfield et Walukiewicz, le mu-calcul est une des logiques les plus importantes pour la vérification de modèles ; elle est expressive tout en ayant de bonnes propriétés algorithmiques. Le mu-calcul (propositionnel et modal) a d'abord été introduit par Dana Scott et Jaco de Bakker puis a été étendu dans sa version moderne par Dexter Kozen. Cette logique permet de décrire les propriétés des systèmes de transition d'états et de les vérifier. De nombreuses logiques temporelles (telles que CTL* ou ses fragments très usités comme ou LTL) sont des fragments du mu-calcul. Une manière algébrique de voir le mu-calcul est de le considérer comme une algèbre de fonctions monotones sur un treillis complet, les opérateurs étant une composition fonctionnelle plus des points fixes ; de ce point de vue, le mu-calcul agit sur le treillis de l'algèbre des ensembles. La sémantique des jeux du mu-calcul est liée aux jeux à deux joueurs à information parfaite, notamment les jeux de parité. Soient deux ensembles de symbole P (les propositions) et A (les actions) et V un ensemble énumérable infini de variables. L'ensemble des formules du mu-calcul (propositionnel et modal) est défini inductivement de la façon suivante : chaque proposition est une formule ; chaque variable est une formule ; si et sont des formules, alors est une formule ; si est une formule, alors est une formule ; si est une formule et est une action, alors est une formule (c'est la formule : « après , nécessairement ») ; si est une formule et une variable, alors est une formule à supposer que chaque occurrence de dans apparaît positivement, c'est-à-dire qu'elle est niée un nombre pair de fois. Les notions de variables liées ou libres sont définies comme d'ordinaire avec qui est le seul opérateur liant une variable.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (4)

Concepts associés (3)

Cours associés (2)

Séances de cours associées (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.

Structure de Kripke

Une structure de Kripke est un modèle de calcul, proche d'un automate fini non déterministe, inventé par Saul Kripke. Elle est utilisée par exemple dans le model checking pour représenter le comportement d'un système. C'est un graphe orienté dont les nœuds représentent les états accessibles du système et dont les arcs représentent les transitions entre les états. Une fonction d'étiquetage fait correspondre à chaque état un ensemble de propositions logiques vraies dans cet état.

Logique temporelle linéaire

En logique, la logique temporelle linéaire (LTL) est une logique temporelle modale avec des modalités se référant au temps. En LTL, on peut coder des formules sur l'avenir d'un chemin infini dans un système de transitions, par exemple une condition finira par être vraie, une condition sera vraie jusqu'à ce qu'une autre devienne vraie, etc. Cette logique est plus faible que la logique CTL*, qui permet d'exprimer des conditions sur des ramifications de chemins et pas seulement sur un seul chemin.

Logique temporelle

La logique temporelle est une branche de la logique mathématique et plus précisément de la logique modale, qui est formalisée de plusieurs manières. La caractéristique commune de ces formalisations réside en l'ajout de modalités (autrement dit de « transformateurs de prédicats ») liées au temps ; par exemple, une formule typique de la logique modale est la formule , qui se lit : « la formule est satisfaite jusqu'à ce que la formule le soit » et qui signifie que l'on cherche à garantir qu'une certaine propriété (ici ) est satisfaite pendant tout le temps qui court avant qu'une autre formule (ici ) le soit.

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

Musique modale et tonale

Explore la musique modale et tonale, en analysant des exemples de musique populaire comme les Beatles 'Norwegian Wood' pour comprendre les échelles, les toniques et les modes.

Architecture et société: Innovations, Critique et Résistance AR-365: Theory and architectural culture

Explore le rôle de l'architecture et des architectes dans la société moderne, en se demandant si les architectes peuvent façonner la société ou si l'architecture est déterminée par les conditions sociales, politiques et économiques.

Résoudre les jeux de parité dans la pratique

Explore les aspects pratiques de la résolution des jeux de parité, y compris les stratégies gagnantes, les algorithmes, la complexité, le déterminisme et les approches heuristiques.