|Abstract of Paper|
A polynomial-time algorithm for deciding true concurrency equivalences of Basic Parallel Processes
by Slawomir Lasota
A polynomial-time algorithm is presented to decide distributed bisimilarity of Basic Parallel Processes. As a direct conclusion, several other non-interleaving semantic equivalences are also decidable in polynomial time for this class of process, since they coincide with distributed bisimilarity.