2026-07-24T11:52:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12830 2024-03-06T10:50:48Z ddc:004 open_access

On the Axiomatisability of Parallel Composition: A Journey in the Spectrum Aceto, Luca Castiglioni, Valentina Ingólfsdóttir, Anna Luttik, Bas Pedersen, Mathias Ruggaard Axiomatisation Parallel composition Linear time-branching time spectrum This paper studies the existence of finite equational axiomatisations of the interleaving parallel composition operator modulo the behavioural equivalences in van Glabbeek’s linear time-branching time spectrum. In the setting of the process algebra BCCSP over a finite set of actions, we provide finite, ground-complete axiomatisations for various simulation and (decorated) trace semantics. On the other hand, we show that no congruence over that language that includes bisimilarity and is included in possible futures equivalence has a finite, ground-complete axiomatisation. This negative result applies to all the nested trace and nested simulation semantics. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Luca Aceto and Valentina Castiglioni and Anna Ingólfsdóttir and Bas Luttik and Mathias Ruggaard Pedersen 2020 Is Part Of LIPIcs, Volume 171, 31st International Conference on Concurrency Theory (CONCUR 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2020.18 urn:nbn:de:0030-drops-128303 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2020.18 eng https://creativecommons.org/licenses/by/3.0/legalcode