Some problems related to bisimilarity on BPP
Martin Kot · 2004
Jancar has in 2003 shown that bisimilarity on Basic Parallel Processes (BPP) can be decided in polynomial space. Bisimilarity is studied on various subclasses of BPP as well. We present summary of known complexity bounds of some such bisimilarity problems. Moreover is here shown that deciding regularity of a BPP is PSPACE-complete. So far this problem was only known to be PSPACE-hard.