C-graph automatic groups

Elder, Murray; Taback, Jennifer

Title: C-graph automatic groups
Creator: Elder, Murray; Taback, Jennifer
Relation: ARC.FT110100178 http://purl.org/au-research/grants/arc/FT110100178
Relation: Journal of Algebra Vol. 413, p. 289-319
Publisher Link: http://dx.doi.org/10.1016/j.jalgebra.2014.04.021
Publisher: Elsevier
Resource Type: journal article
Date: 2014
Description: 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.
Subject: automatic group; Cayley graph automatic group; context-sensitive language; polynomial time algorithm; counter language
Identifier: http://hdl.handle.net/1959.13/1043495
Identifier: uon:14202
Identifier: ISSN:0021-8693
Language: eng
Full Text
Reviewed

Hits: 1193
Visitors: 1489
Downloads: 306

		Thumbnail	File	Description	Size	Format
View Details Download			ATTACHMENT02	Author final version	471 KB	Adobe Acrobat PDF	View Details Download