Další formáty:
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, s.~9-22.
|