Extended Process Rewrite Systems: Expressiveness and Reachability

• Název česky: Rozšířené procesové přepisovací systémy: Vyjadřovací síla a dosažitelnost
• Autoři: KŘETÍNSKÝ Mojmír; ŘEHÁK Vojtěch; STREJČEK Jan
• Rok publikování: 2004
• Druh: Článek ve sborníku
• Konference: CONCUR 2004 - Concurrency Theory
• Fakulta / Pracoviště MU: Fakulta informatiky
• Obor: Informatika
• Klíčová slova: process rewrite systems; state extension; infinite-state; expressivness; reachability; decidability
• 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 stavově rozšířených 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ů