Highly Undecidable Questions for Process Algebras

Petr Jancar; Jirí Srba

doi:10.7146/brics.v11i8.21833

Highly Undecidable Questions for Process Algebras

Authors

Petr Jancar
Jirí Srba

DOI:

https://doi.org/10.7146/brics.v11i8.21833

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

Downloads

Published

2004-04-11

How to Cite

Jancar, P., & Srba, J. (2004). Highly Undecidable Questions for Process Algebras. BRICS Report Series, 11(8). https://doi.org/10.7146/brics.v11i8.21833