Yin, Qiang 

Title: Two Lower Bounds for BPA

Abstract: Branching bisimilarity of normed Basic Process Algebra (nBPA) was claimed to be EXPTIME-hard in previous papers without any explicit proof. Recently it has been pointed out by Petr Jančar that the claim lacked proper justification. In this work, we develop a new complete proof for the EXPTIME-hardness of branching bisimilarity of nBPA. We also prove that the associated regularity problem of nBPA is PSPACE-hard. This improves previous P-hard result.

Publication: Mingzhang Huang and Qiang Yin. Two Lower Bounds for BPA. CONCUR 2017