Other formats:
BibTeX
LaTeX
RIS
@inproceedings{555145,
author = {Jancar, Petr and Srba, Jiří},
address = {USA},
booktitle = {Proceedings of 3rd IFIP International Conference on Theoretical Computer Science (TCS'04)},
keywords = {high undecidability; process rewrite systems; completeness},
language = {eng},
location = {USA},
pages = {?},
publisher = {Kluwer},
title = {Highly Undecidable Questions for Process Algebras},
url = {http://www.brics.dk/~srba/publ.html},
year = {2004}
}
TY - JOUR
ID - 555145
AU - Jancar, Petr - Srba, Jiří
PY - 2004
TI - Highly Undecidable Questions for Process Algebras
PB - Kluwer
CY - USA
KW - high undecidability
KW - process rewrite systems
KW - completeness
UR - http://www.brics.dk/~srba/publ.html
N2 - 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).
ER -
JANCAR, Petr and Jiří SRBA. Highly Undecidable Questions for Process Algebras. In \textit{Proceedings of 3rd IFIP International Conference on Theoretical Computer Science (TCS'04)}. USA: Kluwer, 2004, p.~?, 14 pp.
|
