Highly Undecidable Questions for Process Algebras

Petr Jancar
Jirí Srba

April 2004

Abstract:

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).

Available as PostScript, PDF, DVI.

Last modified: 2004-04-30 by webmaster.