On the Reachability Set of Automaton Counter Machines

E. V. Kuzmin and D. J. Chalyy

Yaroslavl State University, ul. Sovetskaya 14, Yaroslavl, 150000 Russia

e-mail: kuzmin@uniyar.ac.ru, chaly@uniyar.ac.ru

Received December 15, 2009

Abstract—Properties of automaton counter machines are considered. The set of reachability states of
any automaton one-counter machine is proved to be a semilinear set. An algorithm for constructing this
set is described. In addition, the reachability sets of any reversal-bounded automaton counter machine
and any flat automaton counter machine are also semilinear.

Keywords: abstract counter machines, automaton counter machines, communicating coloring autom-
ata, reachability sets, semilinear sets

DOI: 10.3103/S0146411611070091

Pleiades Publishing home page | journal home page | top

If you have any problems with this server, contact webmaster.