On groups and counter automata

Publication Type:
Journal Article
Citation:
International Journal of Algebra and Computation, 2008, 18 (8), pp. 1345 - 1364
Issue Date:
2008-12-01
Metrics:
Full metadata record
Files in This Item:
Filename Description Size
groups-counter.pdfAccepted Manuscript Version223.68 kB
Adobe PDF
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: