In: Proceedings of CONCUR 2004 - Concurrency Theory: 15th International Conference, London, UK, August 31 - September 3, 2004, pages 355-370. Volume 3170 of Lecture Notes in Computer Science / Philippa Gardner, Nobuko Yoshida (Eds.) --- Springer-Verlag, September 2004.
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 expressive up to bisimulation equivalence 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.