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

Изучается класс формальных языков (ЯАСМ), которые допускаются автоматными счетчиковыми машинами. Показывается, что этот класс замкнут относительно операций объединения, регулярного пересечения, конкатенации, бесконечной итерации, гомоморфизма и обратного гомоморфизма. Отсюда сле¬дует, что он является полным абстрактным семейством языков со всеми выте¬кающими из этого свойствами. Более того, класс АСМ-языков замкнут относительно пересечения и полной подстановки, но незамкнут относительно обращения и дополнения. Для класса ЯАСМ разрешимы проблемы пустоты и распо¬знавания слова языка, заданного автоматной счетчиковой машиной, но нераз¬решимы проблемы включения и эквивалентности языков. Проводится срав¬нение с другими классами языков - регулярными, контекстно-свободными, контекстно-зависимыми языками и языками сетей Петри.

Some properties of formal languages (ACML) of automaton counter machines are investigated. We show that a class of these languages is closed with respect to the following operations: union, intersection by regular sets, concatenation, infinite iteration (Kleene star), homomorphism and inverse homomorphism. This means that the ACML-class is full-AFL (Abstract Family of Languages). Moreover, the class of ACML is closed with respect to intersection and substitution, but not closed with respect to conversion and complementation. We prove that an empty language problem and a word recognition problem are decidable for automaton counter machines, but inclusion and equivalence problems are not decidable. We compare the class of ACML with other formal language classes - regular, context-free, context-sensitive and Petri net languages.

абстрактные счетчиковые машиныавтоматные счетчиковые машинывзаимодействующие раскрашивающие процессыформальные языкиabstract counter machinesautomaton counter machineCommunicating Colouring Automataformal languagesReferencesAbdulla P. A., Cerans K., Jonsson B., Yih-Kuen T. General decidability theorems for infinite-state systems // Proc. 11th IEEE Symp. Logic in Computer Science (LICS'96), 1996. P. 313-321.Abdulla P. A., Cerans K., Jonsson B., Yih-Kuen T. General decidability theorems for infinite-state systems // Proc. 11th IEEE Symp. Logic in Computer Science (LICS'96), 1996. P. 313-321.Aho A. V. Indexed grammars - an extension of context-free grammars // Journal of the ACM (JACM). 1968. Vol. 15, n.4. P. 647-671. (http://doi.acm.org/10.1145/321526.321529)Aho A. V. Indexed grammars - an extension of context-free grammars // Journal of the ACM (JACM). 1968. Vol. 15, n.4. P. 647-671. (http://doi.acm.org/10.1145/321526.321529)Dickson L. E. Finiteness of the odd perfect and primitive abundant numbers with r distinct prime factors // Amer. Journal Math. 1913. 35. P. 413-422.Dickson L. E. Finiteness of the odd perfect and primitive abundant numbers with r distinct prime factors // Amer. Journal Math. 1913. 35. P. 413-422.Finkel A. Reduction and covering of infinite reachability trees // Information and Computation. 1990. 89(2). P. 144-179.Finkel A. Reduction and covering of infinite reachability trees // Information and Computation. 1990. 89(2). P. 144-179.Finkel A., Schnoebelen Ph. Well-structured transition systems everywhere! // Theoretical Computer Science. 2001. 256(1-2). P. 63-92.Finkel A., Schnoebelen Ph. Well-structured transition systems everywhere! // Theoretical Computer Science. 2001. 256(1-2). P. 63-92.Ginsburg S. Algebraic and Automata-Theoretic Properties of Formal Languages. Elsevier Science Inc., 1975.Ginsburg S. Algebraic and Automata-Theoretic Properties of Formal Languages. Elsevier Science Inc., 1975.Ginsburg S., Greibach S. Abstract families of languages, «Studies in Abstract Families of Languages*, Amer. Math. Soc., 87 (1969). P. 1-32. (Русский перевод см. в сборнике «Языки и автоматы». М.:Мир, 1975. С. 233-281.)Ginsburg S., Greibach S. Abstract families of languages, «Studies in Abstract Families of Languages*, Amer. Math. Soc., 87 (1969). P. 1-32. (Русский перевод см. в сборнике «Языки и автоматы». М.:Мир, 1975. С. 233-281.)Hack M. Decision problems for Petri nets and vector addition systems // Project MAC Memo 59. Cambridge, 1975.Hack M. Decision problems for Petri nets and vector addition systems // Project MAC Memo 59. Cambridge, 1975.Hack M. The equality problem for vector addition systems is undecidable // Theoretical Computer Science. 1976. 2(1). P. 77-96.Hack M. The equality problem for vector addition systems is undecidable // Theoretical Computer Science. 1976. 2(1). P. 77-96.Higman G. Ordering by divisibility in Abstract Algebra // Proc. London Math. Soc. 1952. 3(2). P. 326-336.Higman G. Ordering by divisibility in Abstract Algebra // Proc. London Math. Soc. 1952. 3(2). P. 326-336.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., Chalyy D. Ju. Automaton counter machines // Proc. Int. Workshop on Program Understanding (sat. of PSI'09). 2009. P. 1-4.Kuzmin E. V., Sokolov V. A., Chalyy D. Ju. Automaton counter machines // Proc. Int. Workshop on Program Understanding (sat. of PSI'09). 2009. P. 1-4.Mayr R. Lossy counter machines. Tech. Report TUM-I9827, Institut fur Informatik, TUM, Germany, October 1998.Mayr R. Lossy counter machines. Tech. Report TUM-I9827, Institut fur Informatik, TUM, Germany, October 1998.Peterson J. Petri Net Theory and the Modeling of Systems. Prentice-Hall Int., 1981.Peterson J. Petri Net Theory and the Modeling of Systems. Prentice-Hall Int., 1981.Котов В. Е. Сети Петри. М.: Наука, 1984.Котов В. Е. Сети Петри. М.: Наука, 1984.Кузьмин Е. В. Недетерминированные счетчиковые машины // Моделирование и анализ информационных систем. 2003. Т. 10 (2). С. 41-49.Кузьмин Е. В. Недетерминированные счетчиковые машины // Моделирование и анализ информационных систем. 2003. Т. 10 (2). С. 41-49.Кузьмин Е. В., Соколов В. А. Взаимодействующие раскрашивающие процессы // Моделирование и анализ информационных систем. 2004. Т. 11 (2). С. 8-17.Кузьмин Е. В., Соколов В. А. Взаимодействующие раскрашивающие процессы // Моделирование и анализ информационных систем. 2004. Т. 11 (2). С. 8-17.Кузьмин Е. В., Соколов В. А. Структурированные системы переходов. М.: Физ-матлит, 2006. 178 с.Кузьмин Е. В., Соколов В. А. Структурированные системы переходов. М.: Физ-матлит, 2006. 178 с.Кузьмин Е. В., Чалый Д. Ю. Об одном классе счетчиковых машин // Модели¬рование и анализ информационных систем. 2009. Т. 16 (2). С. 75-82.Кузьмин Е. В., Чалый Д. Ю. Об одном классе счетчиковых машин // Модели¬рование и анализ информационных систем. 2009. Т. 16 (2). С. 75-82.Матиясевич Ю. В. Диофантовость перечислимых множеств // ДАН СССР. 1970. Т. 191, № 2. С. 279-282.Матиясевич Ю. В. Диофантовость перечислимых множеств // ДАН СССР. 1970. Т. 191, № 2. С. 279-282.Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. 2-е изд.: Пер. с англ. М.: Вильямс, 2002. 528 с.Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. 2-е изд.: Пер. с англ. М.: Вильямс, 2002. 528 с.

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