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.CONCUR.2020.18
URN: urn:nbn:de:0030-drops-128303
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12830/
Go to the corresponding LIPIcs Volume Portal

Aceto, Luca ; Castiglioni, Valentina ; Ingólfsdóttir, Anna ; Luttik, Bas ; Pedersen, Mathias Ruggaard

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

pdf-format:
LIPIcs-CONCUR-2020-18.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{aceto_et_al:LIPIcs:2020:12830,
  author =	{Luca Aceto and Valentina Castiglioni and Anna Ing{\'o}lfsd{\'o}ttir and Bas Luttik and Mathias Ruggaard Pedersen},
  title =	{{On the Axiomatisability of Parallel Composition: A Journey in the Spectrum}},
  booktitle =	{31st International Conference on Concurrency Theory (CONCUR 2020)},
  pages =	{18:1--18:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-160-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{171},
  editor =	{Igor Konnov and Laura Kov{\'a}cs},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12830},
  URN =		{urn:nbn:de:0030-drops-128303},
  doi =		{10.4230/LIPIcs.CONCUR.2020.18},
  annote =	{Keywords: Axiomatisation, Parallel composition, Linear time-branching time spectrum}
}

Keywords: Axiomatisation, Parallel composition, Linear time-branching time spectrum
Collection: 31st International Conference on Concurrency Theory (CONCUR 2020)
Issue Date: 2020
Date of publication: 26.08.2020

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