CCS with Hennessy's merge has no finite-equational axiomatization

DOI10.1016/J.TCS.2004.10.003zbMath1078.68102OpenAlexW2222296167MaRDI QIDQ1763725

Anna Ingólfsdóttir, Bas Luttik, Luca Aceto, W. J. Fokkink

Publication date: 22 February 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://ir.cwi.nl/pub/14520

zbMATH Keywords

Process algebraCCSConcurrencyBisimulationComplete axiomatizationsEquational logicNon-finitely based algebrasCommunication mergeHennessy mergeLeft merge

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Modal logic (including the logic of norms) (03B45) Applications of universal algebra in computer science (08A70) Algebraic theory of languages and automata (68Q70) Semantics in the theory of computing (68Q55) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Equational classes, universal algebra in model theory (03C05)

Related Items (10)

Are Two Binary Operators Necessary to Obtain a Finite Axiomatisation of Parallel Composition? ⋮ Bisimilarity is not finitely based over BPA with interrupt ⋮ Unique parallel decomposition in branching and weak bisimulation semantics ⋮ Non-finite axiomatisability results via reductions: CSP parallel composition and CCS restriction ⋮ Unnamed Item ⋮ Rule formats for distributivity ⋮ Lifting non-finite axiomatizability results to extensions of process algebras ⋮ Is observational congruence on \(\mu \)-expressions axiomatisable in equational Horn logic? ⋮ On the axiomatisability of priority ⋮ The Quest for Equational Axiomatizations of Parallel Composition: Status and Open Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Free shuffle algebras in language varieties
• Algèbre de processus et synchronisation
• Higher-level synchronising devices in Meije-SCCS
• Modeling concurrency with partial orders
• The equational theory of pomsets
• Nonfinite axiomatizability of the equational theory of shuffle
• Unique decomposition of processes
• Turning SOS rules into equations
• Axiomatizing shuffle and concatenation in languages
• Axiomatizing the subsumption and subword preorders on finite and infinite partial words
• A brief history of process algebra
• TAPSOFT '95: Theory and practice of software development. 6th international joint conference CAAP/FASE, Aarhus, Denmark, May 1995. Proceedings
• Process algebra for synchronous communication
• Algebraic laws for nondeterminism and concurrency
• Axiomatising Finite Concurrent Processes
• Flowgraphs and Flow Algebras
• Process Algebra
• Formal verification of parallel programs
• On “Axiomatising Finite Concurrent Processes”
• Languages under concatenation and shuffling
• Varieties generated by languages with poset operations

This page was built for publication: CCS with Hennessy's merge has no finite-equational axiomatization