On groups and counter automata
- Publication Type:
- Journal Article
- International Journal of Algebra and Computation, 2008, 18 (8), pp. 1345 - 1364
- Issue Date:
We study finitely generated groups whose word problems are accepted by counter automata. We show that a group has word problem accepted by a blind n-counter automaton in the sense of Greibach if and only if it is virtually free abelian of rank n; this result, which answers a question of Gilman, is in a very precise sense an abelian analogue of the MullerSchupp theorem. More generally, if G is a virtually abelian group then every group with word problem recognized by a G-automaton is virtually abelian with growth class bounded above by the growth class of G. We consider also other types of counter automata. © 2008 World Scientific Publishing Company.
Please use this identifier to cite or link to this item: