Publication details

Reachability is decidable for weakly extended process rewrite systems

Authors

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

Year of publication 2009
Type Article in Periodical
Magazine / Source Information and Computation
MU Faculty or unit

Faculty of Informatics

Citation
Web http://dx.doi.org/10.1016/j.ic.2009.01.003
Field Informatics
Keywords process rewrite systems; state extension; infinite-state; (un)decidability; reachability
Description Process Rewrite Systems (PRS) are widely accepted as a formalism for the description of infinite-state systems. It is known that the reachability problem for PRS is decidable. The problem becomes undecidable when PRS are extended with a~finite-state control unit. In this paper we show that the problem remains decidable when PRS are extended with a weak (i.e. acyclic except for self-loops) finite-state control unit. We also present some applications of this decidability result.
Related projects:

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

More info