(Co)inductive Proof Systems for Compositional Proofs in Reachability Logic - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

(Co)inductive Proof Systems for Compositional Proofs in Reachability Logic

Vlad Rusu
  • Fonction : Auteur
  • PersonId : 831452
David Nowak

Résumé

Reachability Logic is a formalism that can be used, among others, for expressing partial-correctness properties of transition systems. In this paper we present three proof systems for this formalism, all of which are sound and complete and inherit the coinductive nature of the logic. The proof systems differ, however, in several aspects. First, they use induction and coinduction in different proportions. The second aspect regards compositionality, broadly meaning their ability to prove simpler formulas on smaller systems, and to reuse those formulas as lemmas for more complex formulas on larger systems. The third aspect is the difficulty of their soundness proofs. We show that the more induction a proof system uses, and the more specialised is its use of coinduction (with respect to our problem domain), the more compositional the proof system is, but the more difficult its soundness proof becomes. We also briefly present mechanisations of these results in the Isabelle/HOL and Coq proof assistants.
Fichier principal
Vignette du fichier
from2019_full.pdf (244.5 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02176456 , version 1 (08-07-2019)
hal-02176456 , version 2 (23-08-2019)

Identifiants

Citer

Vlad Rusu, David Nowak. (Co)inductive Proof Systems for Compositional Proofs in Reachability Logic. Working Formal Methods Symposium, Sep 2019, Timisoara, Romania. pp. 32-47, ⟨10.4204/EPTCS.303.3⟩. ⟨hal-02176456v2⟩
90 Consultations
193 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More