Reachability is decidable for weakly extended process rewrite systems

Investor logo
Investor logo
Investor logo

Warning

This publication doesn't include Faculty of Arts. 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 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.