Towards 'up to context' reasoning about higher-order processes - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2020

Towards 'up to context' reasoning about higher-order processes

Résumé

Proving behavioural equivalences in higher-order languages is a difficult task, because interactions involve complex values, namely terms of the language. In coinductive (i.e., bisimulation-like) techniques for these languages, a useful enhancement is the 'up-to context' reasoning, whereby common pieces of context in related terms are factorised out and erased. In higher-order process languages, however, such techniques are rare, as their soundness is usually delicate and difficult to establish. In this paper we adapt the technique of unique solution of equations, that implicitly captures 'up-to context' reasoning, to the setting of the Higher-order π-calculus. Equations are written and solved with respect to normal bisimilarity, chosen both because of its efficiency — its clauses do not require universal quantifications on terms supplied by the external observer — and because of the challenges it poses on the 'up-to context' reasoning and that already show up when proving its congruence properties.
Fichier principal
Vignette du fichier
hopi-HAL.pdf (472.64 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01857391 , version 1 (15-08-2018)

Identifiants

Citer

Adrien Durier, Daniel Hirschkoff, Davide Sangiorgi. Towards 'up to context' reasoning about higher-order processes. Theoretical Computer Science, 2020, 807, pp.154-168. ⟨10.1016/j.tcs.2019.09.036⟩. ⟨hal-01857391⟩
154 Consultations
139 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More