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.
|
