Proof Search Specifications of the pi-calculus

Tiu Alwen 1 Dale Miller 2, 3
1 Logic and Computation group
College of Engineering and Computer Science
2 PARSIFAL - Proof search and reasoning with logic specifications
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : We specify the operational semantics and bisimulation relations for the finite pi-calculus within a logic that contains the nabla quantifier for encoding generic judgments and definitions for encoding fixed points. Since we restrict to the finite case, the ability of the logic to unfold fixed points allows this logic to be complete for both the inductive nature of operational semantics and the coinductive nature of bisimulation. The nabla quantifier helps with the delicate issues surrounding the scope of variables within pi-calculus expressions and their executions (proofs). We illustrate several merits of the logical specifications permitted by this logic: they are natural and declarative; they contain no side-conditions concerning names of variables while maintaining a completely formal treatment of such variables; differences between late and open bisimulation relations arise from familar logic distinctions; the interplay between the three quantifiers (forall, exists, and nabla) and their scopes can explain the differences between early and late bisimulation and between various modal operators based on bound input and output actions; and proof search involving the application of inference rules, unification, and backtracking can provide complete proof systems for one-step transitions, bisimulation, and satisfaction in modal logic. We also illustrate how one can encode the pi-calculus with replications, in an extended logic with induction and co-induction.
Type de document :
Article dans une revue
ACM Transactions on Computational Logic, Association for Computing Machinery, 2010, 11 (2)
Liste complète des métadonnées

Littérature citée [60 références]  Voir  Masquer  Télécharger
Contributeur : Dale Miller <>
Soumis le : jeudi 10 janvier 2013 - 17:28:31
Dernière modification le : mercredi 14 novembre 2018 - 16:14:01
Document(s) archivé(s) le : jeudi 11 avril 2013 - 04:07:58


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00772571, version 1



Tiu Alwen, Dale Miller. Proof Search Specifications of the pi-calculus. ACM Transactions on Computational Logic, Association for Computing Machinery, 2010, 11 (2). 〈hal-00772571〉



Consultations de la notice


Téléchargements de fichiers