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. s. 433-445. ISBN 3-540-44040-2. 2002.
Další formáty:   BibTeX LaTeX RIS
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
Originální 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
Změnil Změnil: prof. RNDr. Antonín Kučera, Ph.D., učo 2508. Změněno: 22. 11. 2006 17:28.
Anotace
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 VaVNá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ěrNá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ů
VytisknoutZobrazeno: 28. 3. 2024 23:57