Bisimilarity on Basic Parallel Processes

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989592%3A15310%2F22%3A73615429" target="_blank" >RIV/61989592:15310/22:73615429 - isvavai.cz</a>
Result on the web
<a href="https://www.sciencedirect.com/science/article/pii/S0304397521007027" target="_blank" >https://www.sciencedirect.com/science/article/pii/S0304397521007027</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.tcs.2021.11.027" target="_blank" >10.1016/j.tcs.2021.11.027</a>

Result language
angličtina
Original language name
Bisimilarity on Basic Parallel Processes
Original language description
The main aim of this paper is to give a simple transparent proof of the result showing that the problem of bisimulation equivalence on the class of Basic Parallel Processes (BPP), denoted by BPP-Bisim, can be decided by a polynomial-space algorithm. This result (by the author) has been previously only presented in a conference version, in a rather technical form that is not easily readable and verifiable. Since the result has clarified the complexity of the problem BPP-Bisim, namely its PSPACE-completeness (using the lower bound by Srba), and the problem deals with a fundamental behavioural equivalence and with one of the simplest models that naturally extend finite-state systems into infinite-state ones, it seems appropriate to have a transparent version of the proof.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)