Abstract
Bergstra and Klop have shown that bisimilarity has a finite equational axiomatisation over ACP/CCS extended with the binary left and communication merge operators. Moller proved that auxiliary operators are necessary to obtain a finite axiomatisation of bisimilarity over CCS, and Aceto et al. showed that this remains true when Hennessy’s merge is added to that language. These results raise the question of whether there is one auxiliary binary operator whose addition to CCS leads to a finite axiomatisation of bisimilarity. This study provides a negative answer to that question based on three reasonable assumptions.
| Original language | English |
|---|---|
| Title of host publication | 29th EACSL Annual Conference on Computer Science Logic, CSL 2021 |
| Editors | Christel Baier, Jean Goubault-Larrecq |
| Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| ISBN (Electronic) | 9783959771757 |
| DOIs | |
| Publication status | Published - Jan 2021 |
| Event | 29th EACSL Annual Conference on Computer Science Logic, CSL 2021 - Virtual, Ljubljana, Slovenia Duration: 25 Jan 2021 → 28 Jan 2021 |
Publication series
| Name | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 183 |
| ISSN (Print) | 1868-8969 |
Conference
| Conference | 29th EACSL Annual Conference on Computer Science Logic, CSL 2021 |
|---|---|
| Country/Territory | Slovenia |
| City | Virtual, Ljubljana |
| Period | 25/01/21 → 28/01/21 |
Bibliographical note
Funding Information:Funding This work has been supported by the project ‘Open Problems in the Equational Logic of Processes’ (OPEL) of the Icelandic Research Fund (grant No. 196050-051).
Publisher Copyright:
© Luca Aceto, Valentina Castiglioni, Wan Fokkink, Anna Ingólfsdóttir, and Bas Luttik.
Other keywords
- Bisimulation
- CCS
- Equational logic
- Non-finitely based algebras
- Parallel composition