Approximating Weak Bisimilarity of Basic Parallel Processes

Piotr Hofman
(University of Warsaw )
Patrick Totzke
(University of Edinburgh)

This paper explores the well known approximation approach to decide weak bisimilarity of Basic Parallel Processes. We look into how different refinement functions can be used to prove weak bisimilarity decidable for certain subclasses. We also show their limitations for the general case. In particular, we show a lower bound of ω ∗ ω for the approximants which allow weak steps and a lower bound of ω + ω for the approximants that allow sequences of actions. The former lower bound negatively answers the open question of Jančar and Hirshfeld.

In Bas Luttik and Michel A. Reniers: Proceedings Combined 19th International Workshop on Expressiveness in Concurrency and 9th Workshop on Structured Operational Semantics (EXPRESS/SOS 2012), Newcastle upon Tyne, UK, September 3, 2012, Electronic Proceedings in Theoretical Computer Science 89, pp. 99–113.
Published: 12th August 2012.

ArXived at: https://dx.doi.org/10.4204/EPTCS.89.8 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org