2017/02/18 by Qiang Yin, Yin, Qiang, Mingzhang Huang +3
Computer Science · #FOS: Computer and information sciences #Formal Methods in Verification #Logic in Computer Science (cs.LO) #Logic, programming, and type systems #Petri Nets in System Modeling
paper · pdf · doi:10.48550/arxiv.1702.05578
openalex publication_date 2017/02/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Jančar 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.