Informační systém MU
SRBA, Jiří. Strong Bisimilarity of Simple Process Algebras: Complexity Lower Bounds. Acta Informatica, The Netherlands: Springer-Verlag, 2003, vol. 39, No 1, p. 469-499.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Strong Bisimilarity of Simple Process Algebras: Complexity Lower Bounds
Authors SRBA, Jiří (203 Czechia, guarantor).
Edition Acta Informatica, The Netherlands, Springer-Verlag, 2003.
Other information
Original language English
Type of outcome article in a journal
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Netherlands
Confidentiality degree is not subject to a state or trade secret
WWW URL
RIV identification code RIV/00216224:14330/03:00008470
Organization unit Faculty of Informatics
Keywords in English infinite-state systems; bisimilarity; complexity
Tags bisimilarity, complexity, infinite-state systems
Changed by Changed by: Mgr. Jiří Srba, Ph.D., učo 2841. Changed: 26/5/2004 13:37.
Abstract
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.
Links
GA201/03/1161, research and development projectName: Verifikace nekonečně stavových systémů
Investor: Czech Science Foundation, Standard Projects
MSM 143300001, plan (intention)Name: Nesekvenční modely výpočtů - kvantové a souběžné distribuované modely výpočetních procesů
Investor: Ministry of Education, Youth and Sports of the CR, Research Intents
Displayed: 5/7/2020 10:16