Comparing Expressibility of Normed BPA and Normed BPP Processes.

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Autoři	ČERNÁ Ivana KŘETÍNSKÝ Mojmír KUČERA Antonín
Rok publikování	1999
Druh	Článek v odborném periodiku
Časopis / Zdroj	Acta informatica
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
Obor	Počítačový hardware a software
Klíčová slova	concurrency; bisimilarity; infinite-state systems
Popis	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.
Související projekty:	Meze algoritmické verifikovatelnosti nekonečně stavových systémů Rozhodnutelné problémy v algebrách procesů Nesekvenční modely výpočtů -- kvantové a souběžné distribuované modely výpočetních procesů