Back to Search Start Over

An intensionally fully-abstract sheaf model for pi (expanded version)

Authors :
Eberhart, Clovis
Hirschowitz, Tom
Seiller, Thomas
Laboratoire de Mathématiques (LAMA)
Centre National de la Recherche Scientifique (CNRS)-Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry])
Institut des Hautes Etudes Scientifiques (IHES)
IHES
ANR-10-BLAN-0305,PiCoq,Vérification Formelle de Composants Distribués(2010)
ANR-11-BS02-0010,RECRE,Réalisabilité pour la logique classique, la concurrence, les références et la réécriture(2011)
Source :
Logical Methods in Computer Science, Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2017, 13 (4), pp.9. ⟨10.23638/LMCS-13(4:9)2017⟩
Publication Year :
2017
Publisher :
HAL CCSD, 2017.

Abstract

International audience; Following previous work on CCS, we propose a compositional model for the π-calculus in which processes are interpreted as sheaves on certain simple sites. Such sheaves are a concurrent form of innocent strategies, in the sense of Hyland-Ong/Nickau game semantics. We define an analogue of fair testing equivalence in the model and show that our interpretation is intensionally fully abstract for it. That is, the interpretation preserves and reflects fair testing equivalence; and furthermore, any innocent strategy is fair testing equivalent to the interpretation of some process. The central part of our work is the construction of our sites, relying on a combinatorial presentation of π-calculus traces in the spirit of string diagrams.

Details

Language :
English
ISSN :
18605974
Database :
OpenAIRE
Journal :
Logical Methods in Computer Science, Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2017, 13 (4), pp.9. ⟨10.23638/LMCS-13(4:9)2017⟩
Accession number :
edsair.arXiv.dedup...e95337f801fbe4f4d419b7649e2311f3