maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State Universitymais-953Research ArticleОригинальные статьиArticlesО множестве достижимости автоматных трехсчетчиковых машинOn a reachability set of automaton 3-counter machinesКузьминЕ. В.KuzminE. V.kuzmin@uniyar.ac.ruЧалыйД. Ю.ChalyyD. J.chaly@uniyar.ac.ruЯрославский государственный университет им. П.Г. ДемидоваRussian Federation2009200920091637784Copyright © Кузьмин Е.В., Чалый Д.Ю., 20092009Кузьмин Е.В., Чалый Д.Ю.Kuzmin E.V., Chalyy D.J.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/953

Доказывается, что существуют абстрактные счетчиковые машины, принадлежащие классу автоматных трехсчетчиковых машин, множество достижимости которых не является полулинейным.

In this paper we prove the existence of automaton 3-counter machines which have non-semilinear reachability sets.

абстрактные счетчиковые машиныавтоматные счетчиковые машинывзаимодействующие раскрашивающие автоматымножества достижимостиполулинейные множестваabstract counter machinesautomaton counter machineCommunicating Colouring Automatareachability setssemilinear setsReferencesFinkel 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.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.Finkel A., Sutre G. Decidability of Reachability Problems for Classes of Two-Counter Automata // In STACS 2000, LNCS 1770, Springer, 2000. P. 346-357.Finkel A., Sutre G. Decidability of Reachability Problems for Classes of Two-Counter Automata // In STACS 2000, LNCS 1770, Springer, 2000. P. 346-357.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/6102Hopcroft 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/6102Kouzmm E. V., Sokolov V.A. Communicating Colouring Automata // Proc. Int. Workshop on Program Understanding (sat. of PSI'03), 2003. P. 40-46.Kouzmm E. V., Sokolov V.A. Communicating Colouring Automata // Proc. Int. Workshop on Program Understanding (sat. of PSI'03), 2003. P. 40-46.Гинзбург С. Математическая теория контекстно-свободных языков. М.: Мир, 1970. 328 с.Гинзбург С. Математическая теория контекстно-свободных языков. М.: Мир, 1970. 328 с.Кузьмин Е. В., Соколов В. А. Взаимодействующие раскрашивающие процессы // Моделирование и анализ информационных систем. 2004. Т. 11, №2. С. 8 -17.Кузьмин Е. В., Соколов В. А. Взаимодействующие раскрашивающие процессы // Моделирование и анализ информационных систем. 2004. Т. 11, №2. С. 8 -17.Кузьмин Е. В., Чалый Д. Ю. Об одном классе счетчиковых машин // Моделирование и анализ информационных систем. 2009. Т. 16, №2. С. 75 - 82.Кузьмин Е. В., Чалый Д. Ю. Об одном классе счетчиковых машин // Моделирование и анализ информационных систем. 2009. Т. 16, №2. С. 75 - 82.Минский М. Вычисления и автоматы. М.: Мир, 1971. 268 c.Минский М. Вычисления и автоматы. М.: Мир, 1971. 268 c.Mayr R. Lossy counter machines. Tech. Report TUM-I9827, Institut fu?r Informatik, TUM, Germany, October 1998.Mayr R. Lossy counter machines. Tech. Report TUM-I9827, Institut fu?r Informatik, TUM, Germany, October 1998.

The authors declare that there are no conflicts of interest present.