Technical Report No. 181 - Abstract

Richard Mayr
Weak Bisimilarity and Regularity of BPA is EXPTIME-hard

We show that checking weak bisimulation equivalence of two context-free processes (also called BPA-processes) is EXPTIME-hard, even under the condition that the processes are normed. Furthermore, checking weak regularity (finiteness up to weak bisimilarity) for context-free processes is EXPTIME-hard as well.