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.

Durier A., Hirschkoff D., Sangiorgi D. (2020). Towards ‘up to context’ reasoning about higher-order processes. THEORETICAL COMPUTER SCIENCE, 807, 154-168 [10.1016/j.tcs.2019.09.036].

Towards ‘up to context’ reasoning about higher-order processes

Durier A.
;
Sangiorgi D.
2020

Abstract

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.
2020
Durier A., Hirschkoff D., Sangiorgi D. (2020). Towards ‘up to context’ reasoning about higher-order processes. THEORETICAL COMPUTER SCIENCE, 807, 154-168 [10.1016/j.tcs.2019.09.036].
Durier A.; Hirschkoff D.; Sangiorgi D.
File in questo prodotto:
File Dimensione Formato  
DStcs.pdf

Open Access dal 27/09/2021

Tipo: Postprint
Licenza: Licenza per Accesso Aperto. Creative Commons Attribuzione - Non commerciale - Non opere derivate (CCBYNCND)
Dimensione 514.78 kB
Formato Adobe PDF
514.78 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/730880
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact