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/