CONCUR 2004 START ConferenceManager    

Extended Process Rewrite Systems: Expressiveness and Reachability

Mojmir Kretinsky, Vojtech Rehak, Jan Strejcek

Presented at Fifteenth International Conference on Concurrency Theory (CONCUR 2004), London, England, 31 August - 3 September, 2004


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.

START Conference Manager (V2.47.4)