Technical Reports
The report FIMU-RS-2002-01
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.
