Geodesic
On languages of automaton counter machines
Modelirovanie i analiz informacionnyh sistem, Tome 17 (2010) no. 2, pp. 48-71.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: abstract counter machines, automaton counter machine, Communicating Colouring Automata, formal languages. 
@article{MAIS_2010_17_2_a3,
     author = {E. V. Kuz'min and D. Yu. Chalyi},
     title = {On languages of automaton counter machines},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {48--71},
     publisher = {mathdoc},
     volume = {17},
     number = {2},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2010_17_2_a3/}
}
TY  - JOUR
AU  - E. V. Kuz'min
AU  - D. Yu. Chalyi
TI  - On languages of automaton counter machines
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2010
SP  - 48
EP  - 71
VL  - 17
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2010_17_2_a3/
LA  - ru
ID  - MAIS_2010_17_2_a3
ER  - 
%0 Journal Article
%A E. V. Kuz'min
%A D. Yu. Chalyi
%T On languages of automaton counter machines
%J Modelirovanie i analiz informacionnyh sistem
%D 2010
%P 48-71
%V 17
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2010_17_2_a3/
%G ru
%F MAIS_2010_17_2_a3
E. V. Kuz'min; D. Yu. Chalyi. On languages of automaton counter machines. Modelirovanie i analiz informacionnyh sistem, Tome 17 (2010) no. 2, pp. 48-71. http://geodesic.mathdoc.fr/item/MAIS_2010_17_2_a3/

[1] V. E. Kotov, Seti Petri, Nauka, M., 1984 | MR

[2] A. V. Aho, “Indexed grammars — an extension of context-free grammars”, Journal of the ACM (JACM), 15:4 (1968), 647–671 | DOI | MR | Zbl

[3] P. A. Abdulla, K. Čerāns, B. Jonsson, T. Yih-Kuen, “General decidability theorems for infinite-state systems”, Logic in Computer Science (LICS'96), Proc. 11th IEEE Symp, 1996, 313–321 | MR

[4] L. E. Dickson, “Finiteness of the odd perfect and primitive abundant numbers with $r$ distinct prime factors”, Amer. Journal Math., 35 (1913), 413–422 | DOI | MR | Zbl

[5] A. Finkel, “Reduction and covering of infinite reachability trees”, Information and Computation, 89:2 (1990), 144–179 | DOI | MR | Zbl

[6] A. Finkel, Ph. Schnoebelen, “Well-structured transition systems everywhere!”, Theoretical Computer Science, 256:1-2 (2001), 63–92 | DOI | MR | Zbl

[7] S. Ginsburg, Algebraic and Automata-Theoretic Properties of Formal Languages, Elsevier Science Inc., 1975 | MR | Zbl

[8] S. Ginsburg, S. Greibach, “Abstract families of languages, Studies in Abstract Families of Languages”, Amer. Math. Soc., 87 (1969), 1–32 ; Yazyki i avtomaty, Mir, M., 1975, 233–281 | MR | MR

[9] M. Hack, Decision problems for Petri nets and vector addition systems, Project MAC Memo 59, Cambridge, 1975

[10] M. Hack, “The equality problem for vector addition systems is undecidable”, Theoretical Computer Science, 2:1 (1976), 77–96 | DOI | MR

[11] G. Higman, “Ordering by divisibility in Abstract Algebra”, Proc. London Math. Soc., 3:2 (1952), 326–336 | DOI | MR | Zbl

[12] E. V. Kouzmin, V. A. Sokolov, “Communicating Colouring Automata”, Proc. Int. Workshop on Program Understanding (sat. of PSI'03), 2003, 40–46

[13] E. V. Kuzmin, V. A. Sokolov, D. Ju. Chalyy, “Automaton counter machines”, Proc. Int. Workshop on Program Understanding (sat. of PSI'09), 2009, 1–4

[14] R. Mayr, Lossy counter machines, Tech. Report TUM-I9827, Institut für Informatik, TUM, Germany, October 1998

[15] J. Peterson, Petri Net Theory and the Modeling of Systems, Prentice-Hall Int., 1981 | MR | Zbl

[16] E. V. Kuzmin, “Nedeterminirovannye schetchikovye mashiny”, Modelirovanie i analiz informatsionnykh sistem, 10:2 (2003), 41–49 | MR

[17] E. V. Kuzmin, V. A. Sokolov, “Vzaimodeistvuyuschie raskrashivayuschie protsessy”, Modelirovanie i analiz informatsionnykh sistem, 11:2 (2004), 8–17

[18] E. V. Kuzmin, V. A. Sokolov, Strukturirovannye sistemy perekhodov, Fizmatlit, M., 2006, 178 pp. | MR

[19] E. V. Kuzmin, D. Yu. Chalyi, “Ob odnom klasse schetchikovykh mashin”, Modelirovanie i analiz informatsionnykh sistem, 16:2 (2009), 75–82 | MR

[20] Yu. V. Matiyasevich, “Diofantovost perechislimykh mnozhestv”, DAN SSSR, 191:2 (1970), 279–282 | Zbl

[21] D. Khopkroft, R. Motvani, D. Ulman, Vvedenie v teoriyu avtomatov, yazykov i vychislenii, 2-e izd., per. s angl., Vilyams, M., 2002, 528 pp.