Other formats:
BibTeX
LaTeX
RIS
@article{492121,
author = {Srba, Jiří},
article_location = {The Netherlands},
article_number = {1},
keywords = {infinite-state systems; bisimilarity; complexity},
language = {eng},
journal = {Acta Informatica},
title = {Strong Bisimilarity of Simple Process Algebras: Complexity Lower Bounds},
url = {http://www.brics.dk/~srba/publ.html},
volume = {39},
year = {2003}
}
TY - JOUR
ID - 492121
AU - Srba, Jiří
PY - 2003
TI - Strong Bisimilarity of Simple Process Algebras: Complexity Lower Bounds
JF - Acta Informatica
VL - 39
IS - 1
SP - 469-499
EP - 469-499
PB - Springer-Verlag
KW - infinite-state systems
KW - bisimilarity
KW - complexity
UR - http://www.brics.dk/~srba/publ.html
N2 - We study bisimilarity and regularity problems of simple process algebras. In particular, we show PSPACE-hardness of the following problems: (i) strong bisimilarity of Basic Parallel Processes (BPP), (ii) strong bisimilarity of Basic Process Algebra (BPA), (iii) strong regularity of BPP, and (iv) strong regularity of BPA. We also demonstrate NL-hardness of strong regularity problems for the normed subclasses of BPP and BPA. Bisimilarity problems of simple process algebras are introduced in a general framework of process rewrite systems, and a uniform description of the new techniques used for the hardness proofs is provided.
ER -
SRBA, Jiří. Strong Bisimilarity of Simple Process Algebras: Complexity Lower Bounds. Online. \textit{Acta Informatica}. The Netherlands: Springer-Verlag, 2003, vol.~39, No~1, p.~469-499, [citováno 2024-04-24]
|
