On a reachability set of automaton 3-counter machines
Abstract
In this paper we prove the existence of automaton 3-counter machines which have non-semilinear reachability sets.
About the Authors
E. V. Kuzmin
Ярославский государственный университет им. П.Г. Демидова
Russian Federation
Russian Federation
D. J. Chalyy
Ярославский государственный университет им. П.Г. Демидова
Russian Federation
Russian Federation
References
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.
Review
For citations:
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.)
Views:
484
Email this article 