## Paper: Strong Bisimilarity on Basic Parallel Processes is PSPACE-complete (at LICS 2003)

**Petr Jančar**

### Abstract

The paper shows an algorithmwhich, given a Basic Parallel Processes (BPP) system, constructs a set of linear mappings which characterize the (strong) bisimulation equivalence on the system. Though the number of the constructed mappings can be exponential, they can be generated in polynomial space; this shows that the problem of deciding bisimulation equivalence on BPP is in PSPACE. Combining with the PSPACE-hardness result by Srba, PSPACE-completeness is thus established.

### BibTeX

@InProceedings{Janar-StrongBisimilarityo, author = {Petr Jančar}, title = {Strong Bisimilarity on Basic Parallel Processes is PSPACE-complete}, booktitle = {Proceedings of the Eighteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2003)}, year = {2003}, month = {June}, pages = {218--227}, location = {Ottawa, Canada}, publisher = {IEEE Computer Society Press} }