On the decidability of boundedness problems for counter Minsky machines
Abstract
In the paper the decidability of boundedness problems for counter Minsky machines is investigated. It is proved, that for Minsky machines with two counters the boundedness is partial decidable, but for the total boundedness problem does not even exist a semidecision algorithm. On the other hand, for one-counter Minsky machines all these problems are polinomial (quantitatively of local machine states) decidable.
About the Authors
E. V. Kuzmin
Ярославский государственный университет
Russian Federation
Russian Federation
D. Ju. Chalyy
Ярославский государственный университет
Russian Federation
Russian Federation
References
1. Кларк, Э.М. Верификация моделей программ: Model Checking / Э.М. Кларк, О. Грамберг, Д. Пелед. - МЦНМО, 2002. - 416 с.
2. Котов, В.Е. Сети Петри / В.Е. Котов - М.: Наука, 1984. - 160 с.
3. Котов, В.Е. Теория схем программ /В.Е. Котов, В. К. Сабельфельд. - М.: Наука, 1991. - 248 с.
4. Кузьмин, Е. В. Структурированные системы переходов / Е. В. Кузьмин, В. А. Соколов. - М.: ФИЗ-МАТЛИТ, 2006. - 178 с.
5. Минский, М. Вычисления и автоматы / М. Минский - М.: Мир, 1971. - 268 с.
6. Хопкрофт, Д. Введение в теорию автоматов, языков и вычислений / Д. Хопкрофт, Р. Мотвани, Д. Уль¬ман. - 2-е изд.: Пер. с англ. - М.: Вильямс, 2002. - 528 с.
7. Chitic, C. On validation of XML streams using finite state machines / C. Chitic, D. Rosu. - WebDB, Paris, 2004. - P. 85-90.
8. Demri, S. Model checking freeze LTL over one-counter automata / S. Demri, R. Lazic, A. Sangnier // Proceedings of the 11th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS'08), LNCS. - 2008. To appear. (http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/DLS-fossacs08.pdf).
9. Dufourd, C. Boundedness of Reset P/T nets / C. Dufourd, P. Jancar, Ph. Schnoebelen // Proc. ICALP'99, LNCS 1644. - 1999. - P. 301-310.
10. Lafourcade, P. Intruder deduction for AC-like equational theories with homomorphisms / P. Lafourcade, D. Lugiez, R. Treinen. - RTA'05, LNCS 3467, Springer, 2005. - P. 308-322.
11. Mayr R. Lossy counter machines / R. Mayr // Tech. Report TUM-I9827, Institut fur Informatik, TUM, Germany, October 1998.
12. Wakatsuki, M. Polynomial time identification of strict deterministic restricted one-counter automata in some class from positive data / M. Wakatsuki, K. Teraguchi, E. Tomita. - ICGI 2004, Athens, LNAI 3264, Springer, 2004. - P. 260-272.
Review
For citations:
Kuzmin E.V., Chalyy D.J. On the decidability of boundedness problems for counter Minsky machines. Modeling and Analysis of Information Systems. 2008;15(1):16-26. (In Russ.)
Views:
455
Email this article 