Strong Bisimilarity and Regularity of Basic Process Algebra 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 29th International Colloquium on Automata, Languages and Programming (ICALP'02)
MU Faculty or unit

Faculty of Informatics

Citation
Field Information theory
Keywords bisimilarity checking; complexity; infinite systems
Description Strong bisimilarity and regularity checking problems of Basic Process Algebra (BPA) are decidable, with the complexity upper bounds 2-EXPTIME. On the other hand, no lower bounds were known. In this paper we demonstrate PSPACE-hardness of these problems.
Related projects:

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