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.

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

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