Strong Bisimilarity and Regularity of Basic Parallel Processes is PSPACE-Hard

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

SRBA Jiří

Year of publication 2002
Type Article in Proceedings
Conference Proceedings of 19th International Symposium on Theoretical Aspects of Computer Science (STACS'02)
MU Faculty or unit

Faculty of Informatics

Citation
Field Information theory
Keywords bisimilarity checking; complexity; infinite systems
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.