Model Checking and Theorem Proving

Résumé : Le model checking est une technique de vérification automatique de propriétés de correction de systèmes finis. Normalement, les outils de model checking ont deux caractéristiques remarquables: ils sont automatisés et ils produisent un contre-exemple si le systéme ne satisfait pas la propriété. La Déduction Modulo est une reformulation de la logique des prédicats où certains axiomes—possiblement tous—sont remplacés par des régles de réécriture. Le but de cette dissertation est de donner un encodage de propriétés temporelles exprimées en CTL en des formules du premier ordre, en exprimant l’équivalence logique entre les opérateurs temporels avec des règles de réécriture. De cette manière, les algorithmes de recherche de preuve conçus pour la Déduction Modulo, tels que la Résolution Modulo ou les Tableaux Modulo, peuvent être utilisés pour vérifierdes propriétés temporelles de systèmes de transition finis. Afin d’accomplir le but de résoudre des problèmes de model checking avec un prouveur automatique quelconque, trois travaux sont inclus dans cette dissertation. Premièrement, nous abordons le problème de parcours de graphes en model checking avec des prouveurs automatiques. Nous proposons une façon d’encoder un graphe en tant que formule de manière à ce que le parcours du graphe correspond aux etapes de résolution. Nous présentons ensuite comment formuler les problèmes de model checking comme des formules du premier ordre en Déduction Modulo. La correction et la complétude de notre méthode montre que résoudre des problèmes de model checking CTL avec des prouveurs automatiques est faisable. Enfin, en nous appuyant sur la base théorique du deuxième travail, nous proposons une méthode de model checking symbolique. Cette méthode est implantée dans iProver Modulo, qui est un prouveur automatique du premier ordre qui utilise la Résolution Modulo Polarisée.
Type de document :
Thèse
Computation and Language [cs.CL]. Paris Diderot, 2015. English
Liste complète des métadonnées

Littérature citée [59 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/tel-01251073
Contributeur : Kailiang Ji <>
Soumis le : mardi 19 janvier 2016 - 18:03:00
Dernière modification le : vendredi 25 mai 2018 - 12:02:06
Document(s) archivé(s) le : jeudi 10 novembre 2016 - 21:14:16

Identifiants

  • HAL Id : tel-01251073, version 1

Collections

Citation

Kailiang Ji. Model Checking and Theorem Proving. Computation and Language [cs.CL]. Paris Diderot, 2015. English. 〈tel-01251073〉

Partager

Métriques

Consultations de la notice

271

Téléchargements de fichiers

165