Informační systém Masarykovy univerzity 

Comparing Expressibility of Normed BPA and Normed BPP Processes.

česky | in English

ČERNÁ, Ivana, Mojmír KŘETÍNSKÝ a Antonín KUČERA. Comparing Expressibility of Normed BPA and Normed BPP Processes. Acta informatica, Berlin: Springer-Verlag, 1999, roč. 36, č. 3, s. 233-256. ISSN 0001-5903.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Comparing Expressibility of Normed BPA and Normed BPP Processes.
Autoři ČERNÁ, Ivana (203 Česká republika, garant), Mojmír KŘETÍNSKÝ (203 Česká republika) a Antonín KUČERA (203 Česká republika).
Vydání Acta informatica, Berlin, Springer-Verlag, 1999, 0001-5903.
Další údaje
Originální jazyk angličtina
Typ výsledku Článek v odborném periodiku
Obor Počítačový hardware a software
Stát vydavatele Německo
Utajení není předmětem státního či obchodního tajemství
Impakt faktor Impact factor: 0.321
Kód RIV RIV/00216224:14330/99:00000703
Organizační jednotka Fakulta informatiky
UT WoS 000079817400003
Klíčová slova anglicky concurrency; bisimilarity; infinite-state systems
Štítky bisimilarity, concurrency, infinite-state systems
Změnil Změnila: prof. RNDr. Ivana Černá, CSc., učo 1419. Změněno: 8. 6. 2009 16:18.
Anotace
We present an exact characterization of those transition systems which can be equivalently (up to bisimilarity) defined by the syntax of normed \BPA\ and normed \BPP\ processes. We provide such a characterization for classes of normed BPA and normed BPP processes as well. Next we demonstrate decidability of the problem whether for a given normed \BPA\ process $\Delta$ there is some unspecified normed \BPP\ process $\Delta'$ such that $\Delta$ and $\Delta'$ are bisimilar. The algorithm is polynomial. Furthermore, we show that if the answer to the previous question is positive, then the process $\Delta'$ is effectively constructible. Analogous algorithms are provided for normed \BPP\ processes. Simplified versions of the mentioned algorithms which work for nBPA and nBPP are given too. As a simple consequence we obtain decidability of bisimilarity in the union of normed \BPA\ and normed \BPP\ processes.
Anotace česky
uvádíme přesnou charakterizaci těch přechodových systémů s návěštími, které lze (až na bisimulačni ekvivalenci) vyjádřit jak pomocí syntaxe normovaných BPA procesů a normovaných BPP procesů. Ukazujeme algoritmickou řešitelnost problému, kdy je dán normovaný BPA proces a jest rozhodnout, zda existuje s ním bisimulačně ekvivaletní normovaný BPP proces. Dále ukazujeme, že pokud odpověď na tento problém ANO, pak lze ekvivaletní BPP proces efektivně zkonstruovat.
Návaznosti
GA201/97/0456, projekt VaVNázev: Meze algoritmické verifikovatelnosti nekonečně stavových systémů
Investor: Grantová agentura ČR, Standardní projekty
GA201/98/P046, projekt VaVNázev: Rozhodnutelné problémy v algebrách procesů
Investor: Grantová agentura ČR, Standardní projekty
MSM 143300001, záměrNázev: Nesekvenční modely výpočtů - kvantové a souběžné distribuované modely výpočetních procesů
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Výzkumné záměry
VytisknoutZobrazeno: 15. 12. 2017 01:40

Relevantní odkazy 


Nahoru | Aktuální datum a čas: 15. 12. 2017 01:40, 50. (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