License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2021.8
URN: urn:nbn:de:0030-drops-134425
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13442/
Go to the corresponding LIPIcs Volume Portal

Aceto, Luca ; Castiglioni, Valentina ; Fokkink, Wan ; Ingólfsdóttir, Anna ; Luttik, Bas

Are Two Binary Operators Necessary to Finitely Axiomatise Parallel Composition?

pdf-format:
LIPIcs-CSL-2021-8.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{aceto_et_al:LIPIcs:2021:13442,
  author =	{Luca Aceto and Valentina Castiglioni and Wan Fokkink and Anna Ing{\'o}lfsd{\'o}ttir and Bas Luttik},
  title =	{{Are Two Binary Operators Necessary to Finitely Axiomatise Parallel Composition?}},
  booktitle =	{29th EACSL Annual Conference on Computer Science Logic (CSL 2021)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-175-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{183},
  editor =	{Christel Baier and Jean Goubault-Larrecq},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13442},
  URN =		{urn:nbn:de:0030-drops-134425},
  doi =		{10.4230/LIPIcs.CSL.2021.8},
  annote =	{Keywords: Equational logic, CCS, bisimulation, parallel composition, non-finitely based algebras}
}

Keywords: Equational logic, CCS, bisimulation, parallel composition, non-finitely based algebras
Collection: 29th EACSL Annual Conference on Computer Science Logic (CSL 2021)
Issue Date: 2021
Date of publication: 13.01.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI