Partially-commutative context-free processes

Publikationstyp
Conference Paper
Date Issued
2009-10-16
Sprache
English
Author(s)
Czerwiński, Wojciech  
Fröschle, Sibylle B.  orcid-logo
Lasota, Sławomir  
TORE-URI
http://hdl.handle.net/11420/11274
First published in
Lecture notes in computer science  
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
20th International Conference on Concurrency Theory (CONCUR 2009)  
Publisher DOI
10.1007/978-3-642-04081-8_18
Scopus ID
2-s2.0-70349878672
Publisher
Springer
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.