A characterisation of open bisimilarity using an intuitionistic modal logic
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 ch...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2018
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/89457 http://hdl.handle.net/10220/44959 |
| _version_ | 1826130333395845120 |
|---|---|
| author | Ahrn, Ki Yung Horne, Ross Tiu, Alwen |
| author2 | School of Computer Science and Engineering |
| author_facet | School of Computer Science and Engineering Ahrn, Ki Yung Horne, Ross Tiu, Alwen |
| author_sort | Ahrn, Ki Yung |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T07:54:45Z |
| format | Journal Article |
| id | ntu-10356/89457 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T07:54:45Z |
| publishDate | 2018 |
| record_format | dspace |
| spelling | ntu-10356/894572020-03-07T11:49:00Z A characterisation of open bisimilarity using an intuitionistic modal logic Ahrn, Ki Yung Horne, Ross Tiu, Alwen School of Computer Science and Engineering Bisimulation Modal Logic 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. MOE (Min. of Education, S’pore) Published version 2018-06-05T08:57:05Z 2019-12-06T17:25:56Z 2018-06-05T08:57:05Z 2019-12-06T17:25:56Z 2017 Journal Article Ahn, K. Y., Horne, R., & Tiu, A. (2017). A Characterisation of Open Bisimulation using an Intuitionistic Modal Logic. Leibniz International Proceedings in Informatics, 85, 7-. https://hdl.handle.net/10356/89457 http://hdl.handle.net/10220/44959 10.4230/LIPIcs.CONCUR.2017.7 en Leibniz International Proceedings in Informatics © 2017 Ki Yung Ahn, Ross Horne, and Alwen Tiu; licensed under Creative Commons License CC-BY 28th International Conference on Concurrency Theory (CONCUR 2017). 17 p. application/pdf |
| spellingShingle | Bisimulation Modal Logic Ahrn, Ki Yung Horne, Ross Tiu, Alwen A characterisation of open bisimilarity using an intuitionistic modal logic |
| title | A characterisation of open bisimilarity using an intuitionistic modal logic |
| title_full | A characterisation of open bisimilarity using an intuitionistic modal logic |
| title_fullStr | A characterisation of open bisimilarity using an intuitionistic modal logic |
| title_full_unstemmed | A characterisation of open bisimilarity using an intuitionistic modal logic |
| title_short | A characterisation of open bisimilarity using an intuitionistic modal logic |
| title_sort | characterisation of open bisimilarity using an intuitionistic modal logic |
| topic | Bisimulation Modal Logic |
| url | https://hdl.handle.net/10356/89457 http://hdl.handle.net/10220/44959 |
| work_keys_str_mv | AT ahrnkiyung acharacterisationofopenbisimilarityusinganintuitionisticmodallogic AT horneross acharacterisationofopenbisimilarityusinganintuitionisticmodallogic AT tiualwen acharacterisationofopenbisimilarityusinganintuitionisticmodallogic AT ahrnkiyung characterisationofopenbisimilarityusinganintuitionisticmodallogic AT horneross characterisationofopenbisimilarityusinganintuitionisticmodallogic AT tiualwen characterisationofopenbisimilarityusinganintuitionisticmodallogic |