Highly Undecidable Questions for Process Algebras
Petr Jančar, Jiři Srba Brics · Kluwer Academic Publishers eBooks · 2006
Weshow Σ 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 π 1 1 -hardness of weak ω-trace equivalence for the (sub)classes BPA (basic process algebra) and BPP (basic parallel processes).