On the Complexity of Semantic Equivalences for Pushdown Automata and BPA

KUČERA, Antonín and 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, p. 433-445. ISBN 3-540-44040-2.

Basic information

Original name

On the Complexity of Semantic Equivalences for Pushdown Automata and BPA

Authors

KUČERA, Antonín (203 Czech Republic, guarantor) and Richard MAYR (276 Germany)
K. Diks, W. Rytter (Eds.).

Edition

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

Publisher

Springer

---

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

20206 Computer hardware and architecture

Country of publisher

Germany

Confidentiality degree

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

RIV identification code

RIV/00216224:14330/02:00006374

Organization unit

Faculty of Informatics

ISBN

3-540-44040-2

UT WoS

000181442200036

Keywords in English

verification; concurrency; weak bisimilarity; infinite-state systems

Tags

concurrency, infinite-state systems, verification, weak bisimilarity

Tags

International impact, Reviewed

---

Abstract

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.

---

Links

GA201/00/0400, research and development project	Name: Nekonečně stavové souběžné systémy - modely a verifikace Investor: Czech Science Foundation, Infinite state concurrent systems - models and verification
MSM 143300001, plan (intention)	Name: Nesekvenční modely výpočtů - kvantové a souběžné distribuované modely výpočetních procesů Investor: Ministry of Education, Youth and Sports of the CR, Non-sequential Models of Computing -- Quantum and Concurrent Distributed Models of Computing