On groups and counter automata

Elder, M; Kambites, M; Ostheimer, G

On groups and counter automata

Elder, M

Kambites, M Ostheimer, G

Permalink

Publication Type:: Journal Article
Citation:: International Journal of Algebra and Computation, 2008, 18 (8), pp. 1345 - 1364
Issue Date:: 2008-12-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted Manuscript VersionAdobe PDF (223.68 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Elder, M https://orcid.org/0000-0002-2438-3945	en_US
dc.contributor.author	Kambites, M	en_US
dc.contributor.author	Ostheimer, G	en_US
dc.date.issued	2008-12-01	en_US
dc.identifier.citation	International Journal of Algebra and Computation, 2008, 18 (8), pp. 1345 - 1364	en_US
dc.identifier.issn	0218-1967	en_US
dc.identifier.uri	http://hdl.handle.net/10453/97350
dc.description.abstract	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.	en_US
dc.relation.ispartof	International Journal of Algebra and Computation	en_US
dc.relation.isbasedon	10.1142/S0218196708004901	en_US
dc.subject.classification	General Mathematics	en_US
dc.title	On groups and counter automata	en_US
dc.type	Journal Article
utslib.citation.volume	8	en_US
utslib.citation.volume	18	en_US
utslib.for	0101 Pure Mathematics	en_US
utslib.for	0103 Numerical and Computational Mathematics	en_US
utslib.for	0802 Computation Theory and Mathematics	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Science
pubs.organisational-group	/University of Technology Sydney/Faculty of Science/School of Mathematical and Physical Sciences
utslib.copyright.status	open_access
pubs.issue	8	en_US
pubs.publication-status	Published	en_US
pubs.volume	18	en_US

Abstract:

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:

http://hdl.handle.net/10453/97350