Refining Undecidability Border of Weak Bisimilarity. (full version of INFINITY 2005 paper)
KŘETÍNSKÝ, Mojmír, Vojtěch ŘEHÁK a Jan STREJČEK. Refining Undecidability Border of Weak Bisimilarity. (full version of INFINITY 2005 paper). Brno: FI MU, 2005. FIMU-RS-2005-06. |
Další formáty:
BibTeX
LaTeX
RIS
|
Základní údaje | |
---|---|
Originální název | Refining Undecidability Border of Weak Bisimilarity. (full version of INFINITY 2005 paper) |
Název česky | Zjemneni hranice nerozhodnutelnosti pro slabou bisimulaci |
Autoři | KŘETÍNSKÝ, Mojmír (203 Česká republika, garant), Vojtěch ŘEHÁK (203 Česká republika) a Jan STREJČEK (203 Česká republika). |
Vydání | Brno, FIMU-RS-2005-06, 2005. |
Nakladatel | FI MU |
Další údaje | |
---|---|
Originální jazyk | angličtina |
Typ výsledku | Audiovizuální tvorba |
Obor | 10201 Computer sciences, information science, bioinformatics |
Stát vydavatele | Česká republika |
Utajení | není předmětem státního či obchodního tajemství |
WWW | URL |
Kód RIV | RIV/00216224:14330/05:00012581 |
Organizační jednotka | Fakulta informatiky |
Klíčová slova anglicky | process rewrite systems; state extension; infinite-state; (un)decidability; weak bisimulation |
Štítky | (un)decidability, infinite-state, process rewrite systems, state extension, weak bisimulation |
Příznaky | Mezinárodní význam |
Změnil | Změnil: prof. RNDr. Jan Strejček, Ph.D., učo 3366. Změněno: 27. 11. 2006 15:12. |
Anotace |
---|
Weak bisimilarity is one of the most studied behavioural equivalences. This equivalence is undecidable for pushdown processes (PDA), process algebras (PA), and multiset automata (MSA, also known as parallel pushdown processes, PPDA). Its decidability is an open question basic process algebras} (BPA) and basic parallel processes (BPP). We move the undecidability border towards these classes by showing that the equivalence remains undecidable for weakly extended versions of BPA and BPP. |
Anotace česky |
---|
Slaba bisimulace je jednou z nejvice studovanych behavioralnich ekvivalenci. Tato ekvivalence je nerozhodnutelna pro pushdown processes (PDA), process algebras (PA), a multiset automata (MSA, zname tez jako parallel pushdown processes, PPDA). Jeji rozhodnutelnost je otevrenym problemem pro question basic process algebras} (BPA) a basic parallel processes (BPP). Ukazujeme, ze hranici jeji nerozhodnutelnosti lze posunout ke zminenym tridam BPA a BPP, a to tak, tato ekvivalence zustava nerohodnutelnou i pro slabe rozsirene verze BPA a BPP. |
Návaznosti | |
---|---|
GA201/03/1161, projekt VaV | Název: Verifikace nekonečně stavových systémů |
Investor: Grantová agentura ČR, Verifikace nekonečně stavových systémů | |
GD102/05/H050, projekt VaV | Název: Integrovaný přístup k výchově studentů DSP v oblasti paralelních a distribuovaných systémů |
Investor: Grantová agentura ČR, Integrovaný přístup k výchově studentů DSP v oblasti paralelních a distribuovaných systémů | |
MSM0021622419, záměr | Název: Vysoce paralelní a distribuované výpočetní systémy |
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy | |
1ET408050503, projekt VaV | Název: Techniky automatické verifikace a validace softwarových a hardwarových systémů |
Investor: Akademie věd ČR, Techniky automatické verifikace a validace softwarových a hardwarových systémů | |
1M0545, projekt VaV | Název: Institut Teoretické Informatiky |
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky |
VytisknoutZobrazeno: 19. 9. 2024 11:28