JANCAR, Petr a Jiří SRBA. Highly Undecidable Questions for Process Algebras. In Proceedings of 3rd IFIP International Conference on Theoretical Computer Science (TCS'04). USA: Kluwer, 2004. s. ?, 14 s.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Highly Undecidable Questions for Process Algebras
Název česky Vysoce nerozhodnutelne problemy pro algebry procesu
Autoři JANCAR, Petr (203 Česká republika) a Jiří SRBA (203 Česká republika, garant).
Vydání USA, Proceedings of 3rd IFIP International Conference on Theoretical Computer Science (TCS'04), od s. ?, 14 s. 2004.
Nakladatel Kluwer
Další údaje
Originální jazyk angličtina
Typ výsledku Stať ve sborníku
Obor 10201 Computer sciences, information science, bioinformatics
Stát vydavatele Spojené státy
Utajení není předmětem státního či obchodního tajemství
WWW URL
Kód RIV RIV/00216224:14330/04:00010073
Organizační jednotka Fakulta informatiky
UT WoS 000227054700039
Klíčová slova anglicky high undecidability; process rewrite systems; completeness
Štítky completeness, high undecidability, process rewrite systems
Změnil Změnil: Mgr. Jiří Srba, Ph.D., učo 2841. Změněno: 18. 1. 2005 17:32.
Anotace
We show Sigma^1_1-completeness of weak bisimilarity for PA (process algebra), and of weak simulation preorder/equivalence for PDA (pushdown automata), PA and PN (Petri nets). We also show Pi^1_1-hardness of weak omega-trace equivalence for the (sub)classes BPA (basic process algebra) and BPP (basic parallel processes).
Anotace česky
V clanku je ukazana Sigma^1_1 uplnost slabe bisimilarity pro tridu PA a slabeho simulacniho predusporadani/ekvivalence pro zasobnikove automaty, PA a Petriho site. Rovnez jsou studovany problemy slabe omega-jazykove ekvivalence pro BPA a BPP.
Návaznosti
GA201/03/1161, projekt VaVNázev: Verifikace nekonečně stavových systémů
Investor: Grantová agentura ČR, Standardní projekty
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, Výzkumné záměry
VytisknoutZobrazeno: 23. 9. 2020 17:24