maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State Universitymais-1020Research ArticleОригинальные статьиArticlesО множестве достижимости автоматных счетчиковых машинOn a reachability set of automaton counter machinesКузьминЕ. В.KuzminE. V.kuzmin@uniyar.ac.ruЧалыйД. Ю.ChalyyD. J.chaly@uniyar.ac.ruЯрославский государственный университет им. П.Г. ДемидоваRussian Federation2010200320101715264Copyright © Кузьмин Е.В., Чалый Д.Ю., 20102010Кузьмин Е.В., Чалый Д.Ю.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/1020

Исследуются свойства автоматных счетчиковых машин. Доказывается, что множество достижимых состояний любой автоматной односчетчиковой машины является полулинейным множеством. Приводится алгоритм построения этого множества. Кроме того, показывается, что множество достижимости лю¬бой автоматной счетчиковой машины с ограничением на количество перемен направлений роста/убывания значений счетчиков и множество достижимости любой плоской автоматной счетчиковой машины также полулинейны.

абстрактные счетчиковые машиныавтоматные счетчиковые машинывзаимодействующие раскрашивающие автоматымножества достижимостиполулинейные множестваabstract counter machinesautomaton counter machineCommunicating Colouring Automatareachability setssemilinear setsReferencesAnnichini A., Bouajjani A., Sighireanu M. TReX: A tool for reachability analysis of complex systems // LNCS 2102, Springer, 2001. P. 368-372.Annichini A., Bouajjani A., Sighireanu M. TReX: A tool for reachability analysis of complex systems // LNCS 2102, Springer, 2001. P. 368-372.Araki T., Kasami T. Decidable problems on the strong connectivity of Petri net reachability sets // Theoretical Computer Science, 4(1), 1977. P. 99-119.Araki T., Kasami T. Decidable problems on the strong connectivity of Petri net reachability sets // Theoretical Computer Science, 4(1), 1977. P. 99-119.Bardin S., Leroux J., Point G. FAST extended release // LNCS 4144, Springer, 2006. P. 63-66.Bardin S., Leroux J., Point G. FAST extended release // LNCS 4144, Springer, 2006. P. 63-66.Esparza J. Petri nets, commutative context-free grammars, and basic parallel processes // Fundamenta Informatica, 31(1), 1997. P. 13-25.Esparza J. Petri nets, commutative context-free grammars, and basic parallel processes // Fundamenta Informatica, 31(1), 1997. P. 13-25.Finkel A., Leroux J. How to compose Presburger-accelerations: Applications to broadcast protocols // LNCS 2556, Springer, 2002. P. 145-156.Finkel A., Leroux J. How to compose Presburger-accelerations: Applications to broadcast protocols // LNCS 2556, Springer, 2002. P. 145-156.Finkel A., Sangnier A. Reversal-bounded Counter Machines Revisited // LNCS 5162, Springer, 2008. P. 323-334.Finkel A., Sangnier A. Reversal-bounded Counter Machines Revisited // LNCS 5162, Springer, 2008. P. 323-334.Hopcroft J. E., Pansiot 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., Pansiot J. On the Reachability Problem for 5-Dimensional Vector Addition Systems. Computer science technical report. Cornell University, 1976. - http://hdl.handle.net/1813/6102Ibarra O. H. Reversal-bounded multicounter machines and their decision problems // J. ACM, 25(1), 1978. P. 116-133.Ibarra O. H. Reversal-bounded multicounter machines and their decision problems // J. ACM, 25(1), 1978. P. 116-133.Konig D. Theorie der Endlichen und Unendlichen Graphen // Akademische Verlagsgesellschaft, Leipzig, 1936.Konig D. Theorie der Endlichen und Unendlichen Graphen // Akademische Verlagsgesellschaft, Leipzig, 1936.Kouzmin E. V., Sokolov V.A. Communicating Colouring Automata // Proc. Int. Workshop on Program Understanding (sat. of PSI'03), 2003. P. 40-46.Kouzmin E. V., Sokolov V.A. Communicating Colouring Automata // Proc. Int. Workshop on Program Understanding (sat. of PSI'03), 2003. P. 40-46.Kuzmin E. V., Sokolov V. A., Chaly D. Ju. Automaton Counter Machines // Proc. of Int. Workshop on Program Understanding (sat. of PSI'09), 2009. P. 1-4.Kuzmin E. V., Sokolov V. A., Chaly D. Ju. Automaton Counter Machines // Proc. of Int. Workshop on Program Understanding (sat. of PSI'09), 2009. P. 1-4.LASH. http://www.montefiore.ulg.ac.be/~boigelot/research/lashLASH. http://www.montefiore.ulg.ac.be/~boigelot/research/lashLeroux J., Sutre G. Flat counter almost everywhere! // LNCS 3707, Springer, 2005. P. 474-488.Leroux J., Sutre G. Flat counter almost everywhere! // LNCS 3707, Springer, 2005. P. 474-488.Mayr E. W. Persistence of vector replacement systems is decidable // Acta Informatica, 15, 1981. P. 309-318.Mayr E. W. Persistence of vector replacement systems is decidable // Acta Informatica, 15, 1981. P. 309-318.Mayr E. W. An algorithm for the general Petri net reachability problem // SIAM J. Comput., 13(3), 1984. P. 441-460.Mayr E. W. An algorithm for the general Petri net reachability problem // SIAM J. Comput., 13(3), 1984. P. 441-460.Presburger M. Uber die Vollstandigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt / M. Presburger // Sprawozdanie z I Kongresu matematykow krajow slowianskich, Warszawa 1929, Warsaw, 1930. P. 92-101, 395.Presburger M. Uber die Vollstandigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt / M. Presburger // Sprawozdanie z I Kongresu matematykow krajow slowianskich, Warszawa 1929, Warsaw, 1930. P. 92-101, 395.Valk R., Vidal-Naquet G. Petri nets and regular languages // J. Comput. Syst. Sci., 23(3), 1981. P. 299-325.Valk R., Vidal-Naquet G. Petri nets and regular languages // J. Comput. Syst. Sci., 23(3), 1981. P. 299-325.Гинзбург С. Математическая теория контекстно-свободных языков. М.:Мир, 1970. 328 с.Гинзбург С. Математическая теория контекстно-свободных языков. М.:Мир, 1970. 328 с.Кузьмин Е. В., Соколов В. А. Взаимодействующие раскрашивающие процессы // Моделирование и анализ информационных систем. 2004. Т. 11, №2. С. 8-17.Кузьмин Е. В., Соколов В. А. Взаимодействующие раскрашивающие процессы // Моделирование и анализ информационных систем. 2004. Т. 11, №2. С. 8-17.Кузьмин Е. В., Чалый Д. Ю. Об одном классе счетчиковых машин // Модели¬рование и анализ информационных систем. 2009. Т. 16, №2. С. 75-82.Кузьмин Е. В., Чалый Д. Ю. Об одном классе счетчиковых машин // Модели¬рование и анализ информационных систем. 2009. Т. 16, №2. С. 75-82.Кузьмин Е. В. , Чалый Д. Ю. О множестве достижимости автоматных трех-счетчиковых машин // Моделирование и анализ информационных систем. 2009. Т. 16, №3. С. 77-84.Кузьмин Е. В. , Чалый Д. Ю. О множестве достижимости автоматных трех-счетчиковых машин // Моделирование и анализ информационных систем. 2009. Т. 16, №3. С. 77-84.Минский М. Вычисления и автоматы. М.: Мир, 1971. 268 c.Минский М. Вычисления и автоматы. М.: Мир, 1971. 268 c.

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