Další formáty:
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. \textit{Acta Informatica}. The Netherlands: Springer-Verlag, 2003, roč.~39, č.~1, s.~469-499.
|