О разрешимости проблем ограниченности для счетчиковых машин Минского
Аннотация
Исследуется разрешимость проблем ограниченности для счетчиковых машин Минского. Доказывается, что для машин Минского с двумя счетчиками проблема ограниченности лишь частично разрешима, а проблема тотальной ограниченности не является даже частично разрешимой. Для односчет-чиковых машин Минского указанные проблемы разрешимы за время, полиномиально зависящее от общего количества локальных состояний счетчиковой машины.
Об авторах
Е. В. Кузьмин
Ярославский государственный университет
Россия
Россия
Д. Ю. Чалый
Ярославский государственный университет
Россия
Россия
Список литературы
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.
Рецензия
Для цитирования:
Кузьмин Е.В., Чалый Д.Ю. О разрешимости проблем ограниченности для счетчиковых машин Минского. Моделирование и анализ информационных систем. 2008;15(1):16-26.
For citation:
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.)
Просмотров:
459
Послать статью по эл. почте 