Correction TD de Model Checking
Correction TD de Model Checking
Logiques temporelles · exam
Fiche de révisionCorrigé
Rédigée à partir de ce document, puis vérifiée avant publication.
La vivacité (liveness) est fondamentalement différente de la sûreté (safety).
Une propriété de sûreté stipule que "rien de mauvais n'arrive". Si elle est violée, on peut toujours le prouver en observant un préfixe fini de l'exécution (une trace finie où le mauvais événement s'est produit).
Une propriété de vivacité, en revanche, stipule que "quelque chose de bien finira par arriver" (par exemple Fp, "p sera éventuellement vrai"). Si l'on observe une exécution partielle (un préfixe passé) qui ne satisfait pas p, on ne peut pas en déduire que la propriété est fausse pour toute l'exécution, car p pourrait très bien devenir vrai dans le futur. La vivacité ne peut donc pas être réfutée par un simple préfixe fini.
Pour illustrer ces propriétés, imaginez un arbre de calcul (dépliage) dont la racine est l'état courant s0.
AG p (Invariance classique : sur tous les chemins, globalement p).
E(q U p) ou bien E(Fp ∧ Gq) selon l'interprétation exacte. La différence est subtile :
AG AF init (Le corrigé source mentionne AG AF p mais note que l'utilisation d'une proposition spécifique "init" est plus appropriée ici pour marquer l'état).
AG EF init (Partout, il existe un chemin possible ramenant à init).
AG EX true (La sémantique de EX true signifie qu'il y a au moins un état suivant valide. L'imposer partout avec AG garantit qu'aucun état de l'automate n'est un puits sans successeur).
(Note : La correction fournie regroupe implicitement la fin de l'Exercice 5 dans sa propre logique, bien que les titres du document source puissent paraître mélangés. L'Exercice 5 démontrait la redondance : Gp ≡ ¬F¬p, Fp ≡ true U p, et l'impossibilité d'exprimer X et U avec les autres car X impose une observation stricte au pas suivant et U est le seul à combiner deux sous-formules).
Soit σ une exécution, et σ_i le i-ème état de cette exécution.
Expression des nouveaux connecteurs en LTL basique :
Expression de U dans LTL avec U remplacé par W :
Parmi les opérateurs donnés (X, F, G, U, W, U≤k, F∞, G∞), ceux qui correspondent à des propriétés de sûreté (ou sous-classes) sont : X, G, W, U≤k. La justification repose sur le fait que la violation de ces propriétés peut toujours être prouvée à l'aide d'un contre-exemple fini (une exécution partielle qui contredit la règle).
(Note : Le document source ne contient ni les énoncés de la section 3.1, ni leur correction textuelle. Cette question est impossible à résoudre sans le texte d'origine complet de la section 3.1).
(Note : La correction source est tronquée pour cette question. Le principe théorique sous-jacent est que R (Release) est le dual de U (Until). Grâce aux équivalences ¬(p U q) ≡ ¬p R ¬q et ¬(p R q) ≡ ¬p U ¬q, on peut pousser toutes les négations vers le bas de l'arbre syntaxique jusqu'aux propositions atomiques, éliminant ainsi le besoin de ¬ devant des formules complexes).
Cette traduction est plus directe :
Face à une épreuve de Model Checking portant sur les logiques temporelles (LTL, CTL, CTL*) :