О языках автоматных счетчиковых машин
Аннотация
Изучается класс формальных языков (ЯАСМ), которые допускаются автоматными счетчиковыми машинами. Показывается, что этот класс замкнут относительно операций объединения, регулярного пересечения, конкатенации, бесконечной итерации, гомоморфизма и обратного гомоморфизма. Отсюда сле¬дует, что он является полным абстрактным семейством языков со всеми выте¬кающими из этого свойствами. Более того, класс АСМ-языков замкнут относительно пересечения и полной подстановки, но незамкнут относительно обращения и дополнения. Для класса ЯАСМ разрешимы проблемы пустоты и распо¬знавания слова языка, заданного автоматной счетчиковой машиной, но нераз¬решимы проблемы включения и эквивалентности языков. Проводится срав¬нение с другими классами языков - регулярными, контекстно-свободными, контекстно-зависимыми языками и языками сетей Петри.
Об авторах
Е. В. Кузьмин
Ярославский государственный университет им. П.Г. Демидова
Россия
Россия
Д. Ю. Чалый
Ярославский государственный университет им. П.Г. Демидова
Россия
Россия
Список литературы
1. 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.
2. 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)
3. 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.
4. Finkel A. Reduction and covering of infinite reachability trees // Information and Computation. 1990. 89(2). P. 144-179.
5. Finkel A., Schnoebelen Ph. Well-structured transition systems everywhere! // Theoretical Computer Science. 2001. 256(1-2). P. 63-92.
6. Ginsburg S. Algebraic and Automata-Theoretic Properties of Formal Languages. Elsevier Science Inc., 1975.
7. 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.)
8. Hack M. Decision problems for Petri nets and vector addition systems // Project MAC Memo 59. Cambridge, 1975.
9. Hack M. The equality problem for vector addition systems is undecidable // Theoretical Computer Science. 1976. 2(1). P. 77-96.
10. Higman G. Ordering by divisibility in Abstract Algebra // Proc. London Math. Soc. 1952. 3(2). P. 326-336.
11. Kouzmin E. V., Sokolov V.A. Communicating Colouring Automata // Proc. Int. Workshop on Program Understanding (sat. of PSI'03). 2003. P. 40-46.
12. 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.
13. Mayr R. Lossy counter machines. Tech. Report TUM-I9827, Institut fur Informatik, TUM, Germany, October 1998.
14. Peterson J. Petri Net Theory and the Modeling of Systems. Prentice-Hall Int., 1981.
15. Котов В. Е. Сети Петри. М.: Наука, 1984.
16. Кузьмин Е. В. Недетерминированные счетчиковые машины // Моделирование и анализ информационных систем. 2003. Т. 10 (2). С. 41-49.
17. Кузьмин Е. В., Соколов В. А. Взаимодействующие раскрашивающие процессы // Моделирование и анализ информационных систем. 2004. Т. 11 (2). С. 8-17.
18. Кузьмин Е. В., Соколов В. А. Структурированные системы переходов. М.: Физ-матлит, 2006. 178 с.
19. Кузьмин Е. В., Чалый Д. Ю. Об одном классе счетчиковых машин // Модели¬рование и анализ информационных систем. 2009. Т. 16 (2). С. 75-82.
20. Матиясевич Ю. В. Диофантовость перечислимых множеств // ДАН СССР. 1970. Т. 191, № 2. С. 279-282.
21. Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. 2-е изд.: Пер. с англ. М.: Вильямс, 2002. 528 с.
Рецензия
Для цитирования:
Кузьмин Е.В., Чалый Д.Ю. О языках автоматных счетчиковых машин. Моделирование и анализ информационных систем. 2010;17(2):48-71.
For citation:
Kuzmin E.V., Chalyy D.J. On languages of automaton counter machines. Modeling and Analysis of Information Systems. 2010;17(2):48-71. (In Russ.)
Просмотров: 407
Послать статью по эл. почте 