Detailed Information on Publication Record
2004
Highly Undecidable Questions for Process Algebras
JANCAR, Petr and Jiří SRBABasic information
Original name
Highly Undecidable Questions for Process Algebras
Name in Czech
Vysoce nerozhodnutelne problemy pro algebry procesu
Authors
JANCAR, Petr (203 Czech Republic) and Jiří SRBA (203 Czech Republic, guarantor)
Edition
USA, Proceedings of 3rd IFIP International Conference on Theoretical Computer Science (TCS'04), p. ?, 14 pp. 2004
Publisher
Kluwer
Other information
Language
English
Type of outcome
Stať ve sborníku
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
United States of America
Confidentiality degree
není předmětem státního či obchodního tajemství
References:
RIV identification code
RIV/00216224:14330/04:00010073
Organization unit
Faculty of Informatics
UT WoS
000227054700039
Keywords in English
high undecidability; process rewrite systems; completeness
Změněno: 18/1/2005 17:32, Prof. Jiří Srba, Ph.D.
V originále
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).
In Czech
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.
Links
| GA201/03/1161, research and development project |
| ||
| MSM 143300001, plan (intention) |
|