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. Les logiques temporelles sont généralement interprétées dans des structures de Kripke. L'existence de certains chemins dans le graphe est alors considérée comme une éventualité de réalisation de formules.
Soit un ensemble de propositions atomiques, c'est-à-dire des expressions booléennes portant sur des variables, des constantes et des prédicats. On note l'ensemble des parties de .
Une structure de Kripke est un 4-uplet où :
est un ensemble fini d'états ;
est un ensemble d'états initiaux ;
est une relation de transition qui vérifie : pour tout , il existe tel que ;
est une fonction détiquetage ou dinterprétation.
La condition associée à la relation de transition spécifie que chaque état doit avoir un successeur dans , ce qui implique que l'on peut toujours construire un chemin infini dans la structure de Kripke. Cette propriété est importante lorsque l'on traite des systèmes réactifs. Pour modéliser un interblocage dans une structure de Kripke, il suffit de faire boucler l'état d'interblocage sur lui-même.
La fonction d'étiquetage définit pour chaque état l'ensemble de toutes les propositions atomiques qui sont valides dans cet état.
Un chemin dans la structure est une suite d'états tels que pour tout . L'étiquette du chemin est la suite d'ensembles qui peut être vu comme un mot infini sur l'alphabet .
Avec cette définition, une structure de Kripke peut être vue comme un automate de Moore avec un alphabet réduit à un singleton, et dont la fonction de sortie est la fonction d'étiquetage.
thumb|Une structure de Kripke à trois états, avec deux propositions.
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.
Explore la vérification des modèles de détermination du temps, la planification U-Pool, l'analyse des pires temps d'exécution et la vérification statistique des modèles pour les systèmes cyber-physiques.
We introduce formal verification as an approach for developing highly reliable systems. Formal verification finds proofs that computer systems work under all relevant scenarios. We will learn how to u
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.
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.
Computation tree logic (CTL) is a branching-time logic, meaning that its model of time is a tree-like structure in which the future is not determined; there are different paths in the future, any one of which might be an actual path that is realized. It is used in formal verification of software or hardware artifacts, typically by software applications known as model checkers, which determine if a given artifact possesses safety or liveness properties. For example, CTL can specify that when some initial condition is satisfied (e.