2-nested simulation is not finitely equationally axiomatizable

DOI10.1007/3-540-44693-1_4MaRDI QIDQ2762495zbMATH OpenFDO

Authors Luca Aceto, Anna Ingolfsdottir, Wan Fokkink

Publication date 9 January 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2010/20100039

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Review text

2-nested simulation was introduced by Groote and Vaandrager as the coarsest equivalence included in completed trace equivalence for which the tyft/tyxt format is a congruence format. In the linear time-branching time spectrum of van Glabbeek, 2-nested simulation is one of the few equivalences for which no finite equational axiomatization is presented. In this paper we prove that such an axiomatization does not exist for 2-nested simulation. For the entire collection see [Zbl 0958.00036].

Recommendations

• Nested semantics over finite trees are equationally hard
• On Finite Alphabets and Infinite Bases III: Simulation
• Nested semantics over finite trees are equationally hard (invited talk)
• Constrained simulations, nested simulation semantics and counting bisimulations
• Nonaxiomatisability of equivalences over finite state processes

Cited in

(2)

• Nested semantics over finite trees are equationally hard
• Ready to preorder: an algebraic and general proof

This page was built for publication: 2-nested simulation is not finitely equationally axiomatizable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2762495)