Comparing Expressibility of Normed BPA and Normed BPP Processes.

• 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
• 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ů