We study proof techniques for bisimilarity based on unique solution of equations. We draw inspiration from a result by Roscoe in the denotational setting of CSP and for failure semantics, essentially stating that an equation (or a system of equations) whose infinite unfolding never produces a divergence has the unique-solution property. We transport this result onto the operational setting of CCS and for bisimilarity. We then exploit the operational approach to: refine the theorem, distinguishing between different forms of divergence; derive an abstract formulation of the theorems, on generic LTSs; adapt the theorems to other equivalences such as trace equivalence, and to preorders such as trace inclusion. We compare the resulting techniques to enhancements of the bisimulation proof method (the 'up-to techniques'). Finally, we study the theorems in name-passing calculi such as the asynchronous φ-calculus, and revisit the completeness proof of Milner's encoding of the γ-calculus into the φ-calculus for Lévy-Longo Trees. Bisimilarity, unique solution of equations, termination, process calculi.

Divergence and unique solution of equations

Durier, Adrien;Sangiorgi, Davide
2017

Abstract

We study proof techniques for bisimilarity based on unique solution of equations. We draw inspiration from a result by Roscoe in the denotational setting of CSP and for failure semantics, essentially stating that an equation (or a system of equations) whose infinite unfolding never produces a divergence has the unique-solution property. We transport this result onto the operational setting of CCS and for bisimilarity. We then exploit the operational approach to: refine the theorem, distinguishing between different forms of divergence; derive an abstract formulation of the theorems, on generic LTSs; adapt the theorems to other equivalences such as trace equivalence, and to preorders such as trace inclusion. We compare the resulting techniques to enhancements of the bisimulation proof method (the 'up-to techniques'). Finally, we study the theorems in name-passing calculi such as the asynchronous φ-calculus, and revisit the completeness proof of Milner's encoding of the γ-calculus into the φ-calculus for Lévy-Longo Trees. Bisimilarity, unique solution of equations, termination, process calculi.
2017
Leibniz International Proceedings in Informatics, LIPIcs
1
16
Durier, Adrien; Hirschkoff, Daniel; Sangiorgi, Davide
File in questo prodotto:
File Dimensione Formato  
LIPIcs-CONCUR-2017-11.pdf

accesso aperto

Tipo: Versione (PDF) editoriale
Licenza: Licenza per Accesso Aperto. Creative Commons Attribuzione (CCBY)
Dimensione 482.67 kB
Formato Adobe PDF
482.67 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/619239
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? ND
social impact