Decomposition and complexity of hereditary history preserving bisimulation on BPP

Publikationstyp
Conference Paper
Publikationsdatum
2005
Sprache
English
Author
Fröschle, Sibylle B. orcid-logo
Lasota, Sławomir 
TORE-URI
http://hdl.handle.net/11420/11321
First published in
Lecture notes in computer science 
Number in series
3653 LNCS
Start Page
263
End Page
277
Citation
Lecture Notes in Computer Science 3653: 263-277 (2005)
Contribution to Conference
16th International Conference on Concurrency Theory, CONCUR 2005 
Publisher DOI
10.1007/11539452_22
Scopus ID
2-s2.0-27244450160
Publisher
Springer
We propose a polynomial-time decision procedure for hereditary history preserving bisimilarity (hhp-b) on Basic Parallel Processes (BPP). Furthermore, we give a sound and complete equational axiomatization for the equivalence. Both results are derived from a decomposition property of hhp-b, which is the main technical contribution of the paper. Altogether, our results complement previous work on complexity and decomposition of classical and history-preserving bisimilarity on BPP.
DDC Class
004: Informatik