Comparing Expressibility of Normed BPA and Normed BPP Processes.

Varování

Publikace nespadá pod Ústav výpočetní techniky, 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ů