Finitely generated semiautomatic groups

Issue title: In Memory of S. Barry Cooper (1943–2015)

Guest editors: Benedikt Löwe

Article type: Research Article

Authors: Jain, Sanjay^a | Khoussainov, Bakhadyr^b | Stephan, Frank^c

Affiliations: [a] Department of Computer Science, National University of Singapore, 13 Computing Drive, COM1, Singapore 117417, Republic of Singapore. sanjay@comp.nus.edu.sg | [b] Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand. bmk@cs.auckland.ac.nz | [c] Department of Mathematics and Department of Computer Science, National University of Singapore, 10 Lower Kent Ridge Road, S17, Singapore 119076, Republic of Singapore. fstephan@comp.nus.edu.sg

Abstract: The present work shows that Cayley automatic groups are semiautomatic and exhibits some further constructions of semiautomatic groups; as a consequence, various undecidability results for Cayley automatic groups hold also for finitely generated semiautomatic groups. However, in spite of their generality, the word problem of finitely generated semiautomatic groups is still solvable in quadratic time. Furthermore, the present work establishes that every finitely generated group of nilpotency class three is semiautomatic. It remains open whether the finitely generated semiautomatic groups are a strict superclass of the Cayley automatic groups.

Keywords: Nilpotent groups, automatic groups, automatic structures, semiautomatic structures, Cayley automatic groups, semigroups, finitely generated groups

DOI: 10.3233/COM-180089

Journal: Computability, vol. 7, no. 2-3, pp. 273-287, 2018