Options
Normed processes, unique decomposition, and complexity of bisimulation equivalences
Citation Link: https://doi.org/10.15480/882.4034
Publikationstyp
Journal Article
Date Issued
2009-06-18
Sprache
English
Author(s)
TORE-DOI
Volume
239
Issue
C
Start Page
17
End Page
42
Citation
Electronic Notes in Theoretical Computer Science 239 (C): 17-42 (2009-07-01)
Publisher DOI
Scopus ID
Publisher
Elsevier Science
We propose a decision procedure for a general class of normed commutative process rewrite systems and their induced bisimulation equivalences. Our technique is inspired by the polynomial-time algorithm for strong bisimilarity on normed Basic Parallel Processes (BPP), developed by Hirshfeld, Jerrum and Moller. As part of our framework we present a generic unique decomposition result, which we obtain by building on a characterization by Luttik and van Oostrom. We apply our general technique to derive polynomial-time algorithms for strong bisimilarity on normed BPP with communication and for distributed bisimilarity on all BPP with communication. Moreover, our technique yields a PSPACE upper bound for weak and branching bisimilarity on totally normed BPP.
Subjects
Basic Parallel Processes
Bisimulation equivalence
branching bisimulation
distributed bisimulation
unique decomposition
weak bisimulation
DDC Class
004: Informatik
Publication version
publishedVersion
Loading...
Name
1-s2.0-S1571066109001509-main.pdf
Size
470.46 KB
Format
Adobe PDF