Paper: Strong Bisimilarity on Basic Parallel Processes is PSPACE-complete (at LICS 2003)
Authors: Petr JancarAbstract
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{Jancar-StrongBisimilarityo, author = {Petr Jancar}, title = {Strong Bisimilarity on Basic Parallel Processes is PSPACE-complete}, booktitle = {Proceedings of the Eighteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2003}, year = 2003, editor = {Phokion G. Kolaitis}, month = {June}, pages = {218--}, location = {Ottawa, Canada}, publisher = {IEEE Computer Society Press} }