Open AccessThe Saga of the Axiomatization of Parallel Composition
Author(s) -
Luca Aceto,
Anna Ingólfsdóttir
Publication year - 2007
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v14i11.21933
Subject(s) - merge (version control) , nondeterministic algorithm , computer science , process calculus , composition (language) , programming language , pi calculus , concurrency , theoretical computer science , linguistics , parallel computing , philosophy
This paper surveys some classic and recent results on the finite axiomatizability of bisimilarity over CCS-like languages. It focuses, in particular, on non-finite axiomatizability results stemming from the semantic interplay between parallel composition and nondeterministic choice. The paper also highlights the role that auxiliary operators, such as Bergstra and Klop's left and communication merge and Hennessy's merge operator, play in the search for a finite, equational axiomatization of parallel composition both for classic process algebras and for their real-time extensions.