A characterisation of open bisimilarity using an intuitionistic modal logic

Ahn, Ki Yung and Horne, Ross and Tiu, Alwen; Meyer, Roland and Nestmann, Uwe, eds. (2017) A characterisation of open bisimilarity using an intuitionistic modal logic. In: 28th International Conference on Concurrency Theory. Leibniz International Proceedings in Informatics . Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, DEU, 7:1–7:17. ISBN 9783959770484 (https://doi.org/10.4230/LIPIcs.CONCUR.2017.7)

[thumbnail of Ahn-etal-CONCUR-2017-A-characterisation-of-open-bisimilarity-using-an-intuitionistic-modal-logic]
Preview
 Text. Filename: Ahn-etal-CONCUR-2017-A-characterisation-of-open-bisimilarity-using-an-intuitionistic-modal-logic.pdf
Final Published Version
License: Creative Commons Attribution 3.0 logo
Download (579kB)| Preview

Abstract

Open bisimilarity is a strong bisimulation congruence for the pi-calculus. In open bisimilarity, free names in processes are treated as variables that may be instantiated; in contrast to late bisimilarity where free names are constants. An established modal logic due to Milner, Parrow, and Walker characterises late bisimilarity, that is, two processes satisfy the same set of formulae if and only if they are bisimilar. We propose an intuitionistic variation of this modal logic and prove that it characterises open bisimilarity. The soundness proof is mechanised in Abella. The completeness proof provides an algorithm for generating distinguishing formulae, useful for explaining and certifying whenever processes are non-bisimilar.

CORE (COnnecting REpositories)