Informační systém MU
SRBA, Jiří. Completeness Results for Undecidable Bisimilarity Problems. In Proccedings of the 5th International Workshop on Verification of Infinite-State Systems (INFINITY'03). Marseille, France: Universire de Provence, Marseille. s. 9-22. 2004.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Completeness Results for Undecidable Bisimilarity Problems
Název česky Uplnostni vysledky pro nerozhodnutelne bisimulacni problemy
Autoři SRBA, Jiří (203 Česká republika, garant).
Vydání Marseille, France, Proccedings of the 5th International Workshop on Verification of Infinite-State Systems (INFINITY'03), od s. 9-22, 14 s. 2004.
Nakladatel Universire de Provence, Marseille
Další údaje
Originální jazyk angličtina
Typ výsledku Stať ve sborníku
Obor 10201 Computer sciences, information science, bioinformatics
Stát vydavatele Francie
Utajení není předmětem státního či obchodního tajemství
WWW URL
Kód RIV RIV/00216224:14330/04:00010086
Organizační jednotka Fakulta informatiky
Klíčová slova anglicky high undecidability; bisimilarity
Štítky bisimilarity, high undecidability
Změnil Změnil: Prof. Jiří Srba, Ph.D., učo 2841. Změněno: 18. 1. 2005 17:32.
Anotace
We establish Sigma_1^1-completeness (in the analytical hierarchy) of weak bisimilarity checking for infinite-state processes generated by pushdown automata and parallel pushdown automata. The results imply Sigma_1^1-completeness of weak bisimilarity for Petri nets and give a negative answer to the open problem stated by Jancar (CAAP'95): ``does the problem of weak bisimilarity for Petri nets belong to Delta_1^1 ?''
Anotace česky
V clanku je ukazana Sigma^1_1 uplnost slabe bisimilarity pro zasabnikove a paralelni zasobnikove automaty.
Návaznosti
GA201/03/1161, projekt VaVNázev: Verifikace nekonečně stavových systémů
Investor: Grantová agentura ČR, Verifikace nekonečně stavových systémů
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ů
Zobrazeno: 29. 3. 2024 15:18