文章基本信息
- 标题：Highly Undecidable Questions for Process Algebras
- 本地全文：下载
- 作者：Petr Jancar ; Jirí Srba
- 期刊名称：BRICS Report Series
- 印刷版ISSN：0909-0878
- 出版年度：2004
- 卷号：11
- 期号：8
- 出版社：Aarhus University
- 摘要：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).
