KŘETÍNSKÝ, Mojmír, Vojtěch ŘEHÁK and Jan STREJČEK. Extended Process Rewrite Systems: Expressiveness and Reachability. In CONCUR 2004 - Concurrency Theory. LNCS 3170. Berlin, Heidelberg, New York: Springer, 2004. p. 355-370, 16 pp. ISBN 3-540-22940-X.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Extended Process Rewrite Systems: Expressiveness and Reachability
Name in Czech Rozšířené procesové přepisovací systémy: Vyjadřovací síla a dosažitelnost
Authors KŘETÍNSKÝ, Mojmír (203 Czech Republic, guarantor), Vojtěch ŘEHÁK (203 Czech Republic) and Jan STREJČEK (203 Czech Republic).
Edition LNCS 3170. Berlin, Heidelberg, New York, CONCUR 2004 - Concurrency Theory, p. 355-370, 16 pp. 2004.
Publisher Springer
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher United Kingdom of Great Britain and Northern Ireland
Confidentiality degree is not subject to a state or trade secret
RIV identification code RIV/00216224:14330/04:00010262
Organization unit Faculty of Informatics
ISBN 3-540-22940-X
UT WoS 000223795700023
Keywords in English process rewrite systems; state extension; infinite-state; expressivness; reachability; decidability
Tags decidability, expressivness, infinite-state, process rewrite systems, reachability, state extension
Tags Reviewed
Changed by Changed by: doc. RNDr. Vojtěch Řehák, Ph.D., učo 3721. Changed: 11/3/2010 13:41.
Abstract
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.
Abstract (in Czech)
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.
Links
GA201/03/1161, research and development projectName: Verifikace nekonečně stavových systémů
Investor: Czech Science Foundation, Standard Projects
MSM 143300001, plan (intention)Name: Nesekvenční modely výpočtů - kvantové a souběžné distribuované modely výpočetních procesů
Investor: Ministry of Education, Youth and Sports of the CR, Research Intents
PrintDisplayed: 27/9/2020 10:37