KŘETÍNSKÝ, Mojmír, Vojtěch ŘEHÁK a Jan STREJČEK. Reachability is decidable for weakly extended process rewrite systems. Information and Computation. Elsevier, 2009, roč. 207, č. 6, s. 671-680. ISSN 0890-5401. |
Další formáty:
BibTeX
LaTeX
RIS
@article{830834, author = {Křetínský, Mojmír and Řehák, Vojtěch and Strejček, Jan}, article_number = {6}, keywords = {process rewrite systems; state extension; infinite-state; (un)decidability; reachability}, language = {eng}, issn = {0890-5401}, journal = {Information and Computation}, title = {Reachability is decidable for weakly extended process rewrite systems}, url = {http://dx.doi.org/10.1016/j.ic.2009.01.003}, volume = {207}, year = {2009} }
TY - JOUR ID - 830834 AU - Křetínský, Mojmír - Řehák, Vojtěch - Strejček, Jan PY - 2009 TI - Reachability is decidable for weakly extended process rewrite systems JF - Information and Computation VL - 207 IS - 6 SP - 671-680 EP - 671-680 PB - Elsevier SN - 08905401 KW - process rewrite systems KW - state extension KW - infinite-state KW - (un)decidability KW - reachability UR - http://dx.doi.org/10.1016/j.ic.2009.01.003 N2 - 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. ER -
KŘETÍNSKÝ, Mojmír, Vojtěch ŘEHÁK a Jan STREJČEK. Reachability is decidable for weakly extended process rewrite systems. \textit{Information and Computation}. Elsevier, 2009, roč.~207, č.~6, s.~671-680. ISSN~0890-5401.
|