Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{403373, author = {Srba, Jiří}, address = {Holland}, booktitle = {Proceedings of 19th International Symposium on Theoretical Aspects of Computer Science (STACS'02)}, keywords = {bisimilarity checking; complexity; infinite systems}, language = {eng}, location = {Holland}, pages = {535-546}, publisher = {Springer-Verlag}, title = {Strong Bisimilarity and Regularity of Basic Parallel Processes is PSPACE-Hard}, year = {2002} }
TY - JOUR ID - 403373 AU - Srba, Jiří PY - 2002 TI - Strong Bisimilarity and Regularity of Basic Parallel Processes is PSPACE-Hard PB - Springer-Verlag CY - Holland KW - bisimilarity checking KW - complexity KW - infinite systems N2 - 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. ER -
SRBA, Jiří. Strong Bisimilarity and Regularity of Basic Parallel Processes is PSPACE-Hard. In \textit{Proceedings of 19th International Symposium on Theoretical Aspects of Computer Science (STACS'02)}. Holland: Springer-Verlag, 2002, s.~535-546.
|