D 2004

Completeness Results for Undecidable Bisimilarity Problems

SRBA, Jiří

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

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í

Odkazy

Kód RIV

RIV/00216224:14330/04:00010086

Organizační jednotka

Fakulta informatiky

Klíčová slova anglicky

high undecidability; bisimilarity

Štítky

Změněno: 18. 1. 2005 17:32, Prof. Jiří Srba, Ph.D.

Anotace

ORIG CZ

V originále

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 ?''

Česky

V clanku je ukazana Sigma^1_1 uplnost slabe bisimilarity pro zasabnikove a paralelni zasobnikove automaty.

Návaznosti

GA201/03/1161, projekt VaV
Název: Verifikace nekonečně stavových systémů
Investor: Grantová agentura ČR, Verifikace nekonečně stavových systémů
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ů