On the Expressive Power of Extended Process Rewrite Systems
| Authors | |
|---|---|
| Year of publication | 2004 |
| Type | Article in Periodical |
| Magazine / Source | BRICS Report Series |
| MU Faculty or unit | |
| Citation | |
| Web | http://www.brics.dk/RS/04/7/ |
| Field | Informatics |
| Keywords | process rewrite systems; state extension; infinite-state; expressivness; reachability |
| Description | 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. |
| Related projects: |