Options
Partially-commutative context-free processes: expressibility and tractability
Publikationstyp
Journal Article
Date Issued
2010-12-17
Sprache
English
Journal
Volume
209
Issue
5
Start Page
782
End Page
798
Citation
Information and Computation 209 (5): 782-798 (2011-05-01)
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
Elsevier
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 algorithmic 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. Expressibility issue of the new class, in comparison with the normed PA class, is also tackled in the paper.
DDC Class
004: Informatik
More Funding Information
The first and the last author acknowledge a partial support by Polish Government Grant Nos. N206 008 32/0810 and N N206 356036, respectively. The second