2004
On the Expressive Power of Extended Process Rewrite Systems
KŘETÍNSKÝ, Mojmír, Vojtěch ŘEHÁK a Jan STREJČEKZákladní údaje
Originální název
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 (203 Česká republika, garant), Vojtěch ŘEHÁK (203 Česká republika) a Jan STREJČEK (203 Česká republika)
Vydání
BRICS Report Series, Aarhus, Basic Research in Computer Science, 2004, 0909-0878
Další údaje
Jazyk
angličtina
Typ výsledku
Článek v odborném periodiku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Česká republika
Utajení
není předmětem státního či obchodního tajemství
Odkazy
Kód RIV
RIV/00216224:14330/04:00010025
Organizační jednotka
Fakulta informatiky
Klíčová slova anglicky
process rewrite systems; state extension; infinite-state; expressivness; reachability
Změněno: 24. 1. 2005 17:02, doc. RNDr. Vojtěch Řehák, Ph.D.
V originále
We unify a view on three extensions of Process Rewrite Systems (PRS) and compare their and PRS's expressive power. We show that the class of Petri nets is less expressible up to bisimulation than the class of PA processes extended with a finite state control unit. Further we show our main result that the reachability problem for PRS extended with a so called weak finite state unit is decidable.
Česky
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.
Návaznosti
| GA201/03/1161, projekt VaV |
| ||
| MSM 143300001, záměr |
|