Two Lower Bounds for BPA.
2017
Branching bisimilarity on normed Basic Process Algebra (BPA) was claimed to be EXPTIME-hard in previous papers without any explicit proof. Recently it is reminded by Jancar that the claim is not so dependable. In this paper, we develop a new complete proof for EXPTIME-hardness of branching bisimilarity on normed BPA. We also prove the associate regularity problem on normed BPA is PSPACE-hard and in EXPTIME. This improves previous P-hard and NEXPTIME result.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
6
References
2
Citations
NaN
KQI