Decidability Analysis of Self-Stabilization for Infinite-State Systems

Article type: Research Article

Authors: Yen, Hsu-Chun | Yu, Lien-Po

Affiliations: Dept. of Electrical Engineering National Taiwan University Taipei, Taiwan 106, R.O.C. E-mails: yen@cc.ee.ntu.edu.tw; lpyu@seed.net.tw

Abstract: For a variety of infinite-state systems, the problem of deciding whether a given system is self-stabilizing or not is investigated from the decidability viewpoint. We develop a unified strategy through which checking self-stabilization is shown to be decidable for lossy vector addition systems with states, one-counter machines, and conflict-free Petri nets. For lossy counter machines and lossy channel systems, in contrast, the self-stabilization problem is shown to be undecidable.

Keywords: Decidability, infinite-state systems, self-stabilization, Petri nets

Journal: Fundamenta Informaticae, vol. 70, no. 4, pp. 387-402, 2006