On the Expressive Power of Extended Process Rewrite Systems

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

KŘETÍNSKÝ Mojmír ŘEHÁK Vojtěch STREJČEK Jan

Year of publication 2004
Type Article in Periodical
Magazine / Source BRICS Report Series
MU Faculty or unit

Faculty of Informatics

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:

You are running an old browser version. We recommend updating your browser to its latest version.