BPA Bisimilarity is EXPTIME-hard

2012/05/31 by Kiefer, Stefan
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.1205.7041

Abstract

Given a basic process algebra (BPA) and two stack symbols, the BPA bisimilarity problem asks whether the two stack symbols are bisimilar. We show that this problem is EXPTIME-hard.

Related

• Two Lower Bounds for BPA
• Branching Bisimilarity on Normed BPA Is EXPTIME-complete
• Branching Bisimilarity of Normed BPA Processes is in NEXPTIME
• A Polynomial Time Algorithm for Deciding Branching Bisimilarity on Totally Normed BPA
• Branching Bisimilarity Checking for PRS