2026-07-23T10:34:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13442 2024-03-06T10:52:05Z ddc:004 open_access

Are Two Binary Operators Necessary to Finitely Axiomatise Parallel Composition? Aceto, Luca Castiglioni, Valentina Fokkink, Wan Ingólfsdóttir, Anna Luttik, Bas Equational logic CCS bisimulation parallel composition non-finitely based algebras 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Luca Aceto and Valentina Castiglioni and Wan Fokkink and Anna Ingólfsdóttir and Bas Luttik 2021 Is Part Of LIPIcs, Volume 183, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2021.8 urn:nbn:de:0030-drops-134425 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2021.8 eng https://creativecommons.org/licenses/by/3.0/legalcode