On languages of automaton counter machines
Abstract
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.
About the Authors
E. V. Kuzmin
Ярославский государственный университет им. П.Г. Демидова
Russian Federation
Russian Federation
D. Ju. Chalyy
Ярославский государственный университет им. П.Г. Демидова
Russian Federation
Russian Federation
References
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 с.
Review
For citations:
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.)
Views:
510
Email this article 