Abstract
We show Sigma^1_1-completeness of weak bisimilarity for PA (process algebra), and of wek 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) of BPA (basic process algebra) and BPP (basic parallel processes).
| Originalsprog | Engelsk |
|---|---|
| Titel | Proceedings of 3rd IFIP International Conference on Theoretical Computer Science (TCS'04) |
| Forlag | Kluwer Academic Publishers |
| Publikationsdato | 2004 |
| Sider | 507-520 |
| Status | Udgivet - 2004 |
| Begivenhed | Highly Undecidable Questions for Process Algebras - Toulouse, Frankrig Varighed: 23 aug. 2004 → 26 aug. 2004 Konferencens nummer: 3 |
Konference
| Konference | Highly Undecidable Questions for Process Algebras |
|---|---|
| Nummer | 3 |
| Land/Område | Frankrig |
| By | Toulouse |
| Periode | 23/08/2004 → 26/08/2004 |