Complexity of Weak Bisimilarity and Regularity for BPA and BPP
DOI:
https://doi.org/10.7146/brics.v7i16.20143Resumé
It is an open problem whether weak bisimilarity is decidablefor Basic Process Algebra (BPA) and Basic Parallel Processes (BPP). A
PSPACE lower bound for BPA and NP lower bound for BPP have been
demonstrated by Stribrna. Mayr achieved recently a result, saying that
weak bisimilarity for BPP is Pi^P_2-hard. We improve this lower bound to
PSPACE, moreover for the restricted class of normed BPP.
Weak regularity (finiteness) of BPA and BPP is not known to be decidable
either. In the case of BPP there is a Pi^P_2-hardness result by Mayr,
which we improve to PSPACE. No lower bound has previously been established
for BPA. We demonstrate DP-hardness, which in particular
implies both NP and co-NP-hardness.
In each of the bisimulation/regularity problems we consider also the
classes of normed processes.
Downloads
Publiceret
2000-01-16
Citation/Eksport
Srba, J. (2000). Complexity of Weak Bisimilarity and Regularity for BPA and BPP. BRICS Report Series, 7(16). https://doi.org/10.7146/brics.v7i16.20143
Nummer
Sektion
Artikler
Licens
Authors who publish with this journal agree to the following terms:- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).