Open AccessHighly Undecidable Questions for Process Algebras
Author(s) -
Petr Jančar,
Jiřı́ Srba
Publication year - 2004
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v11i8.21833
Subject(s) - process calculus , undecidable problem , equivalence (formal languages) , preorder , petri net , trace (psycholinguistics) , mathematics , completeness (order theory) , discrete mathematics , decidability , algebra over a field , computer science , pure mathematics , programming language , algorithm , mathematical analysis , linguistics , philosophy
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).