Partially-commutative context-free processes
First published in
Number in series
Lecture Notes in Computer Science (5710 LNCS): 259-273 (2009-10-16)
Contribution to Conference
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.
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.