. . "Highly Undecidable Questions for Process Algebras" . "Highly Undecidable Questions for Process Algebras" . "2004-01-01+01:00"^^ . "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)."@en . "2"^^ . "?" . "USA" . "1"^^ . "Toulouse, France" . "[2B73225CFFDE]" . "Highly Undecidable Questions for Process Algebras"@en . "Proceedings of 3rd IFIP International Conference on Theoretical Computer Science (TCS'04)" . . . "Vysoce nerozhodnutelne problemy pro algebry procesu"@cs . . . . "566164" . "V clanku je ukazana Sigma^1_1 uplnost slabe bisimilarity pro tridu PA a slabeho simulacniho predusporadani/ekvivalence pro zasobnikove automaty, PA a Petriho site. Rovnez jsou studovany problemy slabe omega-jazykove ekvivalence pro BPA a BPP."@cs . "Kluwer" . "RIV/00216224:14330/04:00010073" . . "Srba, Ji\u0159\u00ED" . . "Highly Undecidable Questions for Process Algebras"@en . "high undecidability; process rewrite systems; completeness"@en . . . "14"^^ . . "P(GA201/03/1161), Z(MSM 143300001)" . "RIV/00216224:14330/04:00010073!RIV08-MSM-14330___" . . "Jan\u010D\u00E1\u0159, Petr" . . "Vysoce nerozhodnutelne problemy pro algebry procesu"@cs . . "14330" . . "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)." . . .