Back to Search Start Over

On the Axiomatisability of Parallel Composition: A Journey in the Spectrum

On the Axiomatisability of Parallel Composition: A Journey in the Spectrum

Authors :
Luca Aceto and Valentina Castiglioni and Anna Ingólfsdóttir and Bas Luttik and Mathias Ruggaard Pedersen
Aceto, Luca
Castiglioni, Valentina
Ingólfsdóttir, Anna
Luttik, Bas
Pedersen, Mathias Ruggaard
Luca Aceto and Valentina Castiglioni and Anna Ingólfsdóttir and Bas Luttik and Mathias Ruggaard Pedersen
Aceto, Luca
Castiglioni, Valentina
Ingólfsdóttir, Anna
Luttik, Bas
Pedersen, Mathias Ruggaard
Publication Year :
2020

Abstract

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.

Details

Database :
OAIster
Notes :
application/pdf, English
Publication Type :
Electronic Resource
Accession number :
edsoai.on1358727861
Document Type :
Electronic Resource
Full Text :
https://doi.org/10.4230.LIPIcs.CONCUR.2020.18