On the Complexity of Semantic Equivalences for Pushdown Automata and BPA

by Antonín Kučera, Richard Mayr, A full version of the paper presented at MFCS`02. May 2002, 32 pages.

FIMU-RS-2002-01. Available as Postscript, PDF.

Abstract:

We study the complexity of comparing pushdown automata (PDA) and context-free processes (BPA) to finite-state systems, w.r.t. strong and weak simulation preorder/equivalence and strong and weak bisimulation equivalence. We present a complete picture of the complexity of all these problems. In particular, we show that strong and weak simulation preorder (and hence simulation equivalence) is EXPTIME-complete between PDA/BPA and finite-state systems in both directions. For PDA the lower bound even holds if the finite-state system is fixed, while simulation-checking between BPA and any fixed finite-state system is already polynomial. Furthermore, we show that weak (and strong) bisimilarity between PDA and finite-state systems is PSPACE-complete, while strong (and weak) bisimilarity between two (normed) PDAs is EXPTIME-hard.