Decidability Analysis of Self-Stabilization for Infinite-State Systems

• Autorzy: Yen H-C. , Yu L-P.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

decidability; infinite-state systems; self-stabilization; Petri net

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 70, nr 4
• Strony: 387--402
• Opis fizyczny: bibliogr. 18 poz.

Twórcy

autor

Yen H-C.

autor

Yu L-P.

• Dept.of Electrical Engineering, National Taiwan University, Taipei, Taiwan 106, R.O.C.,

Bibliografia

• [1] Abdulla, P., Jonsson, B.: Undecidable verification problems for programs with unreliable channels, Inform. and Comput., 130, 1996, 71-90.
• [2] Alur, R., Dill, D.: A theory of timed automata, Theoret. Comput. Sci., 126, 1994, 183-235.
• [3] Bouajjani, A., Mayr, R.: Model checking lossy vector addition systems, Proc. of STACS'99, 1563, 1999.
• [4] Cécé, G., Finkel, A., Iyer, S.: Unreliable channels are easier to verify than perfect channels, Inform. And Comput., 124(1), 1996, 20-31.
• [5] Cherkasova, L., Howell, R., Rosier, L.: Bounded self-stabilizing Petri nets, Acta Informat., 32, 1995, 189-207.
• [6] Dickson, L.: Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors, Amer. J. Math., 35, 1913, 413-422.
• [7] Dijkstra, E.: Self-stabilizing systems in spite of distributed control, C. ACM, 17, 1974, 643-644.
• [8] Ginsburg, S.: The mathematical theory of context-free languages, McGraw-Hill, 1966.
• [9] Gouda, M., Howell, R., Rosier, L.: The instability of self-stabilization, Acta Informat., 27, 1990, 697-724.
• [10] Herman, T.: A comprehensive bibliography on self-stabilization, Chicago Journal of Theoretical Computer Science, Available from http://www.cs.uiowa.edu/ftp/selfstab/bibliography, 1998.
• [11] Hopcroft, J., Pansiot, J.: On the reachability problem for 5-dimensional vector addition systems, Theoret. Comput. Sci., 8(2), 1979, 135-159.
• [12] Howell, R., Rosier, L.: On questions of fairness and temporal logic for conflict-free Petri nets, Advances in Petri Nets 1988 (G. Rozenberg, Ed.), 340, Springer-Verlag, Berlin, 1988.
• [13] Landweber, L., Robertson, E.: Properties of conflict-free and persistent Petri nets, J. Assoc. Comput. Mach., 25, 1978, 352-364.
• [14] Mayr, R.: Undecidable problems in unreliable computations, Theoret. Comput. Sci., 297(1-3), March 2003, 337-354.
• [15] Presburger, M.: Űber die vollständigkeit eines gewissen systems der arithmetik ganzer Zahlen, Comptes Rendus du I congres de Mathematiciens des Pays Slaves, 1929, 92-101.
• [16] Rosier, L., Yen, H.: Logspace hierarchies, polynomial time and the complexity of fairness problems concerning ω -machines, SIAM J. Computing, 16(5), 1987, 779-807.
• [17] Valk, R., Jantzen, M.: The residue of vector sets with applications to decidability in Petri nets, Acta Informatica, 21, 1985, 643-674.
• [18] Yen, H., Wang, B., Yang, M.: Deciding a class of path formulas for conflict-free Petri nets, Theory of Computing Systems, 30(5), 1997, 475-494.