Extended Process Rewrite Systems: Expressiveness and Reachability
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F04%3A00010262" target="_blank" >RIV/00216224:14330/04:00010262 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Extended Process Rewrite Systems: Expressiveness and Reachability
Original language description
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.
Czech name
Rozšířené procesové přepisovací systémy: Vyjadřovací síla a dosažitelnost
Czech description
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.
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA201%2F03%2F1161" target="_blank" >GA201/03/1161: Verification of infinite-state systems</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2004
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
CONCUR 2004 - Concurrency Theory
ISBN
3-540-22940-X
ISSN
—
e-ISSN
—
Number of pages
16
Pages from-to
355-370
Publisher name
Springer
Place of publication
Berlin, Heidelberg, New York
Event location
London, UK
Event date
Jan 1, 2004
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—