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.
| Original language | English |
|---|---|
| Title of host publication | 28th International Conference on Concurrency Theory |
| Editors | Roland Meyer, Uwe Nestmann |
| Place of Publication | Saarbrücken/Wadern |
| Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| Pages | 7:1–7:17 |
| Number of pages | 17 |
| ISBN (Electronic) | 9783959770484 |
| DOIs | |
| Publication status | Published - 1 Aug 2017 |
| Event | 28th International Conference on Concurrency Theory - Berlin, Germany Duration: 5 Sept 2017 → 8 Sept 2017 |
Publication series
| Name | Leibniz International Proceedings in Informatics |
|---|---|
| Volume | 85 |
| ISSN (Print) | 1868-8969 |
Conference
| Conference | 28th International Conference on Concurrency Theory |
|---|---|
| Abbreviated title | CONCUR 2017 |
| Country/Territory | Germany |
| City | Berlin |
| Period | 5/09/17 → 8/09/17 |
Funding
∗ The authors receive support from MOE Tier 2 grant MOE2014-T2-2-076. support from NTU Start Up grant M4081190.020.
Keywords
- bisimulation
- intuitionistic logic
- modal logic