On languages of automaton counter machines
E. V. Kuz'min, D. Yu. Chalyi
P. G. Demidov Yaroslavl State University
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 machines, automaton counter machine, Communicating Colouring Automata, formal languages.
PDF file (632 kB)
E. V. Kuz'min, D. Yu. Chalyi, “On languages of automaton counter machines”, Model. Anal. Inform. Sist., 17:2 (2010), 48–71
Citation in format AMSBIB
\by E.~V.~Kuz'min, D.~Yu.~Chalyi
\paper On languages of automaton counter machines
\jour Model. Anal. Inform. Sist.
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|