C-graph automatic groups

Elder, M; Taback, J

C-graph automatic groups

Elder, M

Taback, J

Permalink

Publication Type:: Journal Article
Citation:: Journal of Algebra, 2014, 413 pp. 289 - 319
Issue Date:: 2014-09-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted ManuscriptAdobe PDF (316.96 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	Taback, J	en_US
dc.date.issued	2014-09-01	en_US
dc.identifier.citation	Journal of Algebra, 2014, 413 pp. 289 - 319	en_US
dc.identifier.issn	0021-8693	en_US
dc.identifier.uri	http://hdl.handle.net/10453/97346
dc.description.abstract	We generalize the notion of a graph automatic group introduced by Kharlampovich, Khoussainov and Miasnikov by replacing the regular languages in their definition with more powerful language classes. For a fixed language class C, we call the resulting groups C-graph automatic. We prove that the class of C-graph automatic groups is closed under change of generating set, direct and free product for certain classes C. We show that for quasi-realtime counter-graph automatic groups where normal forms have length that is linear in the geodesic length, there is an algorithm to compute normal forms (and therefore solve the word problem) in polynomial time. The class of quasi-realtime counter-graph automatic groups includes all Baumslag-Solitar groups, and the free group of countably infinite rank. Context-sensitive-graph automatic groups are shown to be a very large class, which encompasses, for example, groups with unsolvable conjugacy problem, the Grigorchuk group, and Thompson's groups F, T and V. © 2014 Elsevier Inc.	en_US
dc.relation.ispartof	Journal of Algebra	en_US
dc.relation.isbasedon	10.1016/j.jalgebra.2014.04.021	en_US
dc.subject.classification	General Mathematics	en_US
dc.title	C-graph automatic groups	en_US
dc.type	Journal Article
utslib.citation.volume	413	en_US
utslib.for	0101 Pure 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.publication-status	Published	en_US
pubs.volume	413	en_US

Abstract:

We generalize the notion of a graph automatic group introduced by Kharlampovich, Khoussainov and Miasnikov by replacing the regular languages in their definition with more powerful language classes. For a fixed language class C, we call the resulting groups C-graph automatic. We prove that the class of C-graph automatic groups is closed under change of generating set, direct and free product for certain classes C. We show that for quasi-realtime counter-graph automatic groups where normal forms have length that is linear in the geodesic length, there is an algorithm to compute normal forms (and therefore solve the word problem) in polynomial time. The class of quasi-realtime counter-graph automatic groups includes all Baumslag-Solitar groups, and the free group of countably infinite rank. Context-sensitive-graph automatic groups are shown to be a very large class, which encompasses, for example, groups with unsolvable conjugacy problem, the Grigorchuk group, and Thompson's groups F, T and V. © 2014 Elsevier Inc.

Please use this identifier to cite or link to this item:

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