О множестве достижимости автоматных трехсчетчиковых машин
Аннотация
Доказывается, что существуют абстрактные счетчиковые машины, принадлежащие классу автоматных трехсчетчиковых машин, множество достижимости которых не является полулинейным.
Об авторах
Е. В. Кузьмин
Ярославский государственный университет им. П.Г. Демидова
Россия
Россия
Д. Ю. Чалый
Ярославский государственный университет им. П.Г. Демидова
Россия
Россия
Список литературы
1. Finkel A., Sutre G. An Algorithm Constructing the Semilinear Post* for 2-Dim Reset/Transfer VASS // In MFCS 2000, LNCS 1893, Springer, 2000. P. 353-362.
2. Finkel A., Sutre G. Decidability of Reachability Problems for Classes of Two-Counter Automata // In STACS 2000, LNCS 1770, Springer, 2000. P. 346-357.
3. Hopcroft J. E., Panswt J. On the Reachability Problem for 5-Dimensional Vector Addition Systems. Computer science technical report. Cornell University, 1976. -http://hdl.handle.net/1813/6102
4. Kouzmm E. V., Sokolov V.A. Communicating Colouring Automata // Proc. Int. Workshop on Program Understanding (sat. of PSI'03), 2003. P. 40-46.
5. Гинзбург С. Математическая теория контекстно-свободных языков. М.: Мир, 1970. 328 с.
6. Кузьмин Е. В., Соколов В. А. Взаимодействующие раскрашивающие процессы // Моделирование и анализ информационных систем. 2004. Т. 11, №2. С. 8 -17.
7. Кузьмин Е. В., Чалый Д. Ю. Об одном классе счетчиковых машин // Моделирование и анализ информационных систем. 2009. Т. 16, №2. С. 75 - 82.
8. Минский М. Вычисления и автоматы. М.: Мир, 1971. 268 c.
9. Mayr R. Lossy counter machines. Tech. Report TUM-I9827, Institut fu?r Informatik, TUM, Germany, October 1998.
Рецензия
Для цитирования:
Кузьмин Е.В., Чалый Д.Ю. О множестве достижимости автоматных трехсчетчиковых машин. Моделирование и анализ информационных систем. 2009;16(3):77-84.
For citation:
Kuzmin E.V., Chalyy D.J. On a reachability set of automaton 3-counter machines. Modeling and Analysis of Information Systems. 2009;16(3):77-84. (In Russ.)
Просмотров: 378
Послать статью по эл. почте 