Bisimilarity is not finitely based over BPA with interrupt

DOI10.1016/j.tcs.2006.07.003zbMath1154.68084OpenAlexW2108192909MaRDI QIDQ860878

Sumit Nain, Luca Aceto, W. J. Fokkink, Anna Ingólfsdóttir

Publication date: 9 January 2007

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.07.003

zbMATH Keywords

process algebraequational logicbisimulationexpressivenessconcurrencynon-finitely based algebrasbasic process algebra (BPA)complete axiomatizationsdisruptinterrupt

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Applications of universal algebra in computer science (08A70) 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 (6)

Are Two Binary Operators Necessary to Obtain a Finite Axiomatisation of Parallel Composition? ⋮ On the axiomatisability of priority. III: Priority strikes again ⋮ Non-finite axiomatisability results via reductions: CSP parallel composition and CCS restriction ⋮ Rule formats for distributivity ⋮ Lifting non-finite axiomatizability results to extensions of process algebras ⋮ On the axiomatisability of priority

Uses Software

• ML

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nested semantics over finite trees are equationally hard
• The equational theory of pomsets
• Nonaxiomatisability of equivalences over finite state processes
• CCS with Hennessy's merge has no finite-equational axiomatization
• The max-plus algebra of the natural numbers has no finite equational basis
• On the expressive power of CCS
• Decidability of bisimulation equivalence for process generating context-free languages
• Process algebra for synchronous communication
• Axiomatising Finite Concurrent Processes
• A menagerie of non-finitely based process semantics over BPA* – from ready simulation to completed traces
• Foundations of Software Science and Computation Structures
• Algebra and Coalgebra in Computer Science

This page was built for publication: Bisimilarity is not finitely based over BPA with interrupt