Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{483064, author = {Srba, Jiří}, address = {Netherlands}, booktitle = {Proceedings of 29th International Colloquium on Automata, Languages and Programming (ICALP'02)}, keywords = {bisimilarity checking; complexity; infinite systems}, language = {eng}, location = {Netherlands}, pages = {716-727}, publisher = {Springer-Verlag}, title = {Strong Bisimilarity and Regularity of Basic Process Algebra is PSPACE-Hard}, year = {2002} }
TY - JOUR ID - 483064 AU - Srba, Jiří PY - 2002 TI - Strong Bisimilarity and Regularity of Basic Process Algebra is PSPACE-Hard PB - Springer-Verlag CY - Netherlands KW - bisimilarity checking KW - complexity KW - infinite systems N2 - 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. ER -
SRBA, Jiří. Strong Bisimilarity and Regularity of Basic Process Algebra is PSPACE-Hard. In \textit{Proceedings of 29th International Colloquium on Automata, Languages and Programming (ICALP'02)}. Netherlands: Springer-Verlag, 2002, s.~716-727.
|