On the Complexity of Semantic Equivalences for Pushdown Automata and BPA

KUČERA, Antonín a Richard MAYR. On the Complexity of Semantic Equivalences for Pushdown Automata and BPA. K. Diks, W. Rytter (Eds.). In Proceedings of 27th International Symposium on Mathematical Foundations of Computer Science (MFCS 2002). Berlin: Springer, 2002, s. 433-445. ISBN 3-540-44040-2.

Základní údaje

Originální název

On the Complexity of Semantic Equivalences for Pushdown Automata and BPA

Autoři

KUČERA, Antonín (203 Česká republika, garant) a Richard MAYR (276 Německo)
K. Diks, W. Rytter (Eds.).

Vydání

Berlin, Proceedings of 27th International Symposium on Mathematical Foundations of Computer Science (MFCS 2002), s. 433-445, 2002

Nakladatel

Springer

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

20206 Computer hardware and architecture

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Kód RIV

RIV/00216224:14330/02:00006374

Organizační jednotka

Fakulta informatiky

ISBN

3-540-44040-2

UT WoS

000181442200036

Klíčová slova anglicky

verification; concurrency; weak bisimilarity; infinite-state systems

Štítky

concurrency, infinite-state systems, verification, weak bisimilarity

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

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 PDAs is EXPTIME-hard.

---

Návaznosti

GA201/00/0400, projekt VaV	Název: Nekonečně stavové souběžné systémy - modely a verifikace Investor: Grantová agentura ČR, Nekonečně stavové souběžné systémy - modely a verifikace
MSM 143300001, záměr	Název: Nesekvenční modely výpočtů - kvantové a souběžné distribuované modely výpočetních procesů Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Nesekvenční modely výpočtů -- kvantové a souběžné distribuované modely výpočetních procesů