On the Expressive Power of Extended Process Rewrite Systems

• Název česky: O vyjadřovací síle rozšířených procesových přepisovacích systémů
• Autoři: KŘETÍNSKÝ Mojmír; ŘEHÁK Vojtěch; STREJČEK Jan
• Rok publikování: 2004
• Druh: Článek v odborném periodiku
• Časopis / Zdroj: BRICS Report Series
• Fakulta / Pracoviště MU: Fakulta informatiky
• www: http://www.brics.dk/RS/04/7/
• Obor: Informatika
• Klíčová slova: process rewrite systems; state extension; infinite-state; expressivness; reachability
• Popis: Sjednocujeme pohled na rozšíření procesových přepisovacích systemů a srovnáváme jejich vyjadřovací sílu. Konkrétně v této zprávě ukazujeme, že trída Petriho sítí je vlastní podtřídou třídy procesových algeber (vzhledem k silné bisimulaci). Dále prezentujeme důkaz rozhodnutelnosti problému dosažitelnosti pro procesové přepisovací systémy rozšířené o slabou konečně stavovou jednotku.

Související projekty

• Verifikace nekonečně stavových systémů
• Nesekvenční modely výpočtů -- kvantové a souběžné distribuované modely výpočetních procesů