On groups and counter automata | NOVA. The University of Newcastle's Digital Repository

Home

Description	Size	Format
Author final version	185 KB	Adobe Acrobat PDF	View/Open

Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/926900

Title: On groups and counter automata
Author/Creator: Elder, Murray; Kambites, Mark; Ostheimer, Gretchen
Institution: The University of Newcastle. Faculty of Science & Information Technology, School of Mathematical and Physical Sciences
Description: 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 Muller–Schupp 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.
Relation: International Journal of Algebra and Computation Vol. 18, Issue 8, p. 1345 - 1364
Publisher Link: http://dx.doi.org/10.1142/S0218196708004901
Date: 2008
Publisher: World Scientific Publishing
Keyword(s): word problem; counter language; G-automaton
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/926900
Identifier: ISSN:0218-1967

16 Visitors

24 Hits

NOVA. The University of Newcastle's Digital Repository