We show that the problem of checking whether two processes definable in the syntax of Basic Parallel Processes (BPP) are strongly bisimilar is PSPACE-hard. We also demonstrate that there is a polynomial time reduction from the strong bisimilarity checking problem of regular BPP to the strong regularity (finiteness) checking of BPP. This implies that strong regularity of BPP is also PSPACE-hard.
Stacs 2002 : Symposium on Theoretical Aspects of Computer Science: Annual Symposium on Theoretical Aspects of Computer Science No19, 2002, p. 535-546
Decidability; Finite state machine; Polynomial time; Regularity
Main Research Area:
STACS 2002 : symposium on theoretical aspects of computer science;Annual symposium on theoretical aspects of computer science