On the Expressive Power of
Extended Process Rewrite Systems

Mojmír Kretínský
Vojtech Rehák
Jan Strejcek

April 2004


We provide a unified 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 Process Algebra extended with 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.

Available as PostScript, PDF, DVI.


Last modified: 2004-04-22 by webmaster.