2004
Extended Process Rewrite Systems: Expressiveness and Reachability
KŘETÍNSKÝ, Mojmír, Vojtěch ŘEHÁK a Jan STREJČEKZákladní údaje
Originální název
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 (203 Česká republika, garant), Vojtěch ŘEHÁK (203 Česká republika) a Jan STREJČEK (203 Česká republika)
Vydání
LNCS 3170. Berlin, Heidelberg, New York, CONCUR 2004 - Concurrency Theory, od s. 355-370, 16 s. 2004
Nakladatel
Springer
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Velká Británie a Severní Irsko
Utajení
není předmětem státního či obchodního tajemství
Kód RIV
RIV/00216224:14330/04:00010262
Organizační jednotka
Fakulta informatiky
ISBN
3-540-22940-X
UT WoS
000223795700023
Klíčová slova anglicky
process rewrite systems; state extension; infinite-state; expressivness; reachability; decidability
Štítky
Příznaky
Recenzováno
Změněno: 11. 3. 2010 13:41, 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 expressive power with that of PRS. 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 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.
Návaznosti
| GA201/03/1161, projekt VaV |
| ||
| MSM 143300001, záměr |
|