Options
Partially-commutative context-free processes
Publikationstyp
Conference Paper
Date Issued
2009-10-16
Sprache
English
First published in
Number in series
5710 LNCS
Start Page
259
End Page
273
Citation
Lecture Notes in Computer Science (5710 LNCS): 259-273 (2009-10-16)
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
Springer
ISBN of container
978-3-642-04081-8
978-3-642-04080-1
Bisimulation equivalence is decidable in polynomial time for both sequential and commutative normed context-free processes, known as BPA and BPP, respectively. Despite apparent similarity between the two classes, different techniques were used in each case. We provide one polynomial-time algorithm that works in a superclass of both normed BPA and BPP. It is derived in the setting of partially-commutative context-free processes, a new process class introduced in the paper. It subsumes both BPA and BPP and seems to be of independent interest.
DDC Class
004: Informatik
530: Physik
600: Technik
More Funding Information
The first and the last author acknowledge a partial support by Polish government grants no. N206 008 32/0810 and N N206 356036.