Nonaxiomatisability of equivalences over finite state processes

DOI10.1016/S0168-0072(97)00036-5zbMath0898.03012MaRDI QIDQ1377607

Peter Sewell

Publication date: 1 November 1998

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

process algebraequational logicregular expressionsbehavioural equivalencesequational axiomatizationsnonaxiomatisabilitytrace congruence

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Algebraic theory of languages and automata (68Q70) Semantics in the theory of computing (68Q55) Equational logic, Mal'tsev conditions (08B05) Equational classes, universal algebra in model theory (03C05) Combinatory logic and lambda calculus (03B40)

Related Items (10)

Bisimilarity is not finitely based over BPA with interrupt ⋮ Nested semantics over finite trees are equationally hard ⋮ The equational logic of fixed points ⋮ Theory of interaction ⋮ Embedding Untimed into Timed Process Algebra; the Case for Explicit Termination ⋮ Complete Axiomatization for Divergent-Sensitive Bisimulations in Basic Process Algebra with Prefix Iteration ⋮ Non-deterministic structures of computation ⋮ Is observational congruence on \(\mu \)-expressions axiomatisable in equational Horn logic? ⋮ Non-regular iterators in process algebra ⋮ On the axiomatisability of priority

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A complete inference system for a class of regular behaviours
• Complete systems of \(\mathcal B\)-rational identities
• Iteration theories of synchronization trees
• A complete axiomatisation for observational congruence of finite-state behaviours
• Mathematical foundations of computer science 1993. 18th international symposium, MFCS '93, Gdańsk, Poland, August/September 1993. Proceedings
• A completeness theorem for Kleene algebras and the algebra of regular events
• A complete equational axiomatization for prefix iteration
• The algebra of communicating processes with empty process
• Asynchronous process calculi: The first- and higher-order paradigms
• Axiomatizing prefix iteration with silent steps
• Une remarque sur les systèmes complets d'identités rationnelles
• On the termination of program schemas
• A menagerie of non-finitely based process semantics over BPA* – from ready simulation to completed traces
• Equational axioms for regular sets
• Two Complete Axiom Systems for the Algebra of Regular Events
• On the Forms of the Predicates in the Theory of Constructive Ordinals
• A complete axiomatisation for trace congruence of finite state behaviors

This page was built for publication: Nonaxiomatisability of equivalences over finite state processes