Informační systém Masarykovy univerzity 

Refining Undecidability Border of Weak Bisimilarity.

česky | in English

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, 20 s. ISSN 1571-0661.
Další formáty:   BibTeX LaTeX RIS
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
Originální jazyk angličtina
Typ výsledku Článek ve sborníku
Obor Informatika
Stát vydavatele Nizozemsko
Utajení není předmětem státního či obchodního tajemství
WWW URL
Kód RIV RIV/00216224:14330/06:00015292
Organizační jednotka Fakulta informatiky
ISSN 1571-0661
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
Změnil Změnil: RNDr. Vojtěch Řehák, Ph.D., učo 3721. Změněno: 23. 6. 2009 16:53.
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 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.
Anotace č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 VaVNázev: Integrovaný přístup k výchově studentů DSP v oblasti paralelních a distribuovaných systémů
Investor: Grantová agentura ČR, Doktorské granty
MSM0021622419, záměrNázev: Vysoce paralelní a distribuované výpočetní systémy
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Výzkumné záměry
1ET408050503, projekt VaVNázev: Techniky automatické verifikace a validace softwarových a hardwarových systémů
Investor: Akademie věd ČR, Informační společnost (Národní program výzkumu)
1M0545, projekt VaVNázev: Institut Teoretické Informatiky
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Výzkumná centra (Národní program výzkumu)
VytisknoutZobrazeno: 22. 10. 2017 12:13

Relevantní odkazy 


Nahoru | Aktuální datum a čas: 22. 10. 2017 12:13, 42. (sudý) týden

Kontakty: istech(zavináč/atsign)fi(tečka/dot)muni(tečka/dot)cz, studijní odd., správci práv, is-technici, e-technici, IT podpora | Použití cookies | Více o Informačním systému