Other formats:
BibTeX
LaTeX
RIS
@inproceedings{555232,
author = {Srba, Jiří},
address = {Marseille, France},
booktitle = {Proccedings of the 5th International Workshop on Verification of Infinite-State Systems (INFINITY'03)},
keywords = {high undecidability; bisimilarity},
language = {eng},
location = {Marseille, France},
note = {To appear in ENTCS.},
pages = {9-22},
publisher = {Universire de Provence, Marseille},
title = {Completeness Results for Undecidable Bisimilarity Problems},
url = {http://www.brics.dk/~srba/publ.html},
year = {2004}
}
TY - JOUR
ID - 555232
AU - Srba, Jiří
PY - 2004
TI - Completeness Results for Undecidable Bisimilarity Problems
PB - Universire de Provence, Marseille
CY - Marseille, France
N1 - To appear in ENTCS.
KW - high undecidability
KW - bisimilarity
UR - http://www.brics.dk/~srba/publ.html
N2 - 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 ?''
ER -
SRBA, Jiří. Completeness Results for Undecidable Bisimilarity Problems. In \textit{Proccedings of the 5th International Workshop on Verification of Infinite-State Systems (INFINITY'03)}. Marseille, France: Universire de Provence, Marseille, 2004, p.~9-22.
|
