On the Expressive Power of Extended Process Rewrite Systems

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

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