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. BRICS Notes Series, San Francisco, USA, 2005, roč. 2005, NS-05-4, s. 3-14. ISSN 0909-3206.
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 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í BRICS Notes Series, San Francisco, USA, 2005, 0909-3206.
Další údaje
Originální jazyk angličtina
Typ výsledku Článek v odborném periodiku
Obor Informatika
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:00012580
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, Recenzováno
Změnil Změnil: prof. RNDr. Mojmír Křetínský, CSc., učo 631. Změněno: 4. 12. 2006 16:38.
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 zasobnikove procesy (PDA), procesove algebry (PA), and multimnozinove automaty (MSA, zname tez jako paralelni zasobnikove procesy, PPDA). Jeji rozhodnutelnost je otevrenym problemem pro zakladni procesove algebry (BPA) a zakladni paralelni procesy (BPP). Ukazujeme, ze hranici jeji nerozhodnutelnosti lze posunout ke zminenym tridam BPA a BPP. Konkretne ukazeme, ze tato ekvivalence zustava nerohodnutelnou i pro slabe rozsirene verze BPA a BPP.
Návaznosti
GA201/03/1161, projekt VaVNázev: Verifikace nekonečně stavových systémů
Investor: Grantová agentura ČR, Standardní projekty
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:06

Relevantní odkazy 


Nahoru | Aktuální datum a čas: 22. 10. 2017 12:06, 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