CCS with Hennessy's merge has no finite equational axiomatization

L. Aceto, W.J. Fokkink, A. Ingólfsdóttir, B. Luttik

Onderzoeksoutput: Boek/rapportRapportAcademic

85 Downloads (Pure)


Abstract This paper confirms a conjecture of Bergstra and Klop¿s from 1984 by establishing that the process algebra obtained by adding an auxiliary operator proposed by Hennessy in 1981 to the recursion free fragment of Milner¿s Calculus of Communicationg Systems is not finitely based modulo bisimulation equivalence. Thus Hennessy¿s merge cannot replace the left merge and communication merge operators proposed by Bergstra and Klop, at least if a finite axiomatization of parallel composition is desired. 2000 MATHEMATICS SUBJECT CLASSIFICATION: 08A70, 03B45, 03C05, 68Q10, 68Q45, 68Q55, 68Q70. CR SUBJECT CLASSIFICATION (1991): D.3.1, F.1.1, F.1.2, F.3.2, F.3.4, F.4.1. KEYWORDS AND PHRASES: Concurrency, process algebra, CCS, bisimulation, Hennessy¿s merge, left merge, communication merge, parallel composition, equational logic, complete axiomatizations, non-finitely based algebras.
Originele taal-2Engels
Plaats van productieEindhoven
UitgeverijTechnische Universiteit Eindhoven
Aantal pagina's33
StatusGepubliceerd - 2004

Publicatie series

NaamComputer science reports
ISSN van geprinte versie0926-4515


Duik in de onderzoeksthema's van 'CCS with Hennessy's merge has no finite equational axiomatization'. Samen vormen ze een unieke vingerafdruk.

Citeer dit