1 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University2 BRICS; Department of Computer Science, University of Aarhus3 Freie Universität Berlin · Institute of Computer Science4 Scientific Officer for Information and Communication Technologies (ICT)
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