Refining Undecidability Border of Weak Bisimilarity.

KŘETÍNSKÝ, Mojmír, Vojtěch ŘEHÁK a Jan STREJČEK. Refining Undecidability Border of Weak Bisimilarity. In Proceedings of the 7th International Workshop on Verification of Infinite-State Systems (INFINITY'05). 2006. vyd. Amsterdam, The Netherlands: Elsevier Science, 2006, s. 17-36. ISSN 1571-0661.

Základní údaje

Originální název

Refining Undecidability Border of Weak Bisimilarity.

Název česky

Zjemneni hranice nerozhodnutelnosti slabe bisimulace

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í

2006. vyd. Amsterdam, The Netherlands, Proceedings of the 7th International Workshop on Verification of Infinite-State Systems (INFINITY'05), od s. 17-36, 20 s. 2006

Nakladatel

Elsevier Science

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Nizozemské království

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Kód RIV

RIV/00216224:14330/06:00015292

Organizační jednotka

Fakulta informatiky

ISSN

Klíčová slova anglicky

process rewrite systems; state extension; infinite-state; decidability; weak bisimilarity

Štítky

decidability, infinite-state, process rewrite systems, state extension, weak bisimilarity

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

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 for 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. In fact, we show that the weak bisimulation equivalence problem is undecidable even for normed subclasses of BPA and BPP extended with a finite constraint system.

Česky

Časopisecké vydání sborníku INFINITY2005. Ukazujeme, že slabá bisimulace zůstává nerozhodnutelná i pro slabě rozšířené varianty tříd BPA a BPP.

---

Návaznosti

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