Sage Journals: Discover world-class research

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

Get full access to this article

View all access options for this article.

References

Afshari,

Barmpalias,

S.B

Cooper and

Stephan, Post’s programme for the Ershov hierarchy, Journal of Logic and Computation17 (2007), 1025–1040. doi:10.1093/logcom/exm032.

Berdinsky and

Khoussainov, On automatic transitive graphs, in: Developments in Language Theory – Eighteenth International Conference, DLT 2014, Proceedings, Ekaterinburg, Russia, August 26–29, 2014, LNCS, Vol. 8633, Springer, 2014, pp. 1–12.

Case,

Jain,

Seah and

Stephan, Automatic functions, linear time and learning, Logical Methods in Computer Science9(3) (2013).

S.B.

Cooper, Mathematics, metaphysics and the multiverse, in: Computation, Physics and Beyond – International Workshop on Theoretical Computer Science, WTCS 2012, Revised Selected and Invited Papers, Auckland, New Zealand, 21–24 February 2012, LNCS, Vol. 7160, Springer, 2012, pp. 252–267. Dedicated to Cristian S. Calude on the Occasion of His Sixtieth Birthday.

S.B.

Cooper, The machine as data: A computational view of emergence and definability, Synthese192(7) (2015), 1955–1988. doi:10.1007/s11229-015-0803-4.

D.B.A.

Epstein,

J.W.

Cannon,

D.F.

Holt,

S.V.F.

Levy,

M.S.

Paterson and

W.P.

Thurston, Word Processing in Groups, Jones and Bartlett Publishers, Boston, 1992.

T.V.

Gopal,

Agrawal,

Li and

S.B.

Cooper, A roadmap to TAMC, in: Theory and Applications of Models of Computation – Eleventh Annual Conference, TAMC 2014, Proceedings, Chennai, India, LNCS, Vol. 8402, Springer, 2014, pp. 1–6.

B.R.

Hodgson, Théories décidables par automate fini, Ph.D. thesis, Département de mathématiques et de statistique, Université de Montréal, 1976.

B.R.

Hodgson, Décidabilité par automate fini, Annales des sciences mathématiques du Québec7(1) (1983), 39–57.

10.

Jain,

Khoussainov and

Stephan, Finitely generated semiautomatic groups, in: Pursuit of the Universal, Twelfth Conference on Computability in Europe, CiE 2016, Proceedings, Paris, France, 27 June–1 July 2016, LNCS, Vol. 9709, Springer, 2016, pp. 282–291.

11.

Jain,

Khoussainov,

Stephan,

Teng and

Zou, Semiautomatic structures, Theory of Computing Systems61(4) (2017), 1254–1287. doi:10.1007/s00224-017-9792-7.

12.

Kharlampovich,

Khoussainov and

Miasnikov, From automatic structures to automatic groups, Groups, Geometry and Dynamical Systems8(1) (2014), 157–198.

13.

Khoussainov and

Nerode, Automatic presentations of structures, in: Logic and Computational Complexity, International Workshop, LCC 1994, Proceedings, Indianapolis, Indiana, USA, October 13–16, 1994, LNCS, Vol. 960, Springer, 1995, pp. 367–392. doi:10.1007/3-540-60178-3_93.

14.

K.L.

Manders and

Adleman, NP-complete decision problems for binary quadratics, Journal of Computer and System Sciences16 (1978), 168–184. doi:10.1016/0022-0000(78)90044-2.

15.

Miasnikov and

Šunić, Cayley graph automatic groups are not necessarily Cayley graph biautomatic, in: Language and Automata Theory and Applications – Sixth International Conference, LATA 2012, Proceedings, A Coruña, Spain, March 5–9, 2012,

A.H.

Dediu and

Martín-Vide, eds, LNCS, Vol. 7183, Springer, 2012, pp. 401–407.

16.

Nies, Describing groups, The Bulletin of Symbolic Logic13(3) (2007), 305–339. doi:10.2178/bsl/1186666149.

17.

Nies and Richard , Thomas. FA-presentable groups and rings, Journal of Algebra320 (2008), 569–585. doi:10.1016/j.jalgebra.2007.04.015.

18.

Oliver and

R.M.

Thomas, Automatic presentations for finitely generated groups, in: Twentysecond Annual Symposium on Theoretical Aspects of Computer Science (STACS 2005), Proceedings, Stuttgart, Germany, LNCS, Vol. 3404, Springer, 2005, pp. 693–704.

19.

J.S.

Rose, A Course on Group Theory, Dover Publications, 2012.

20.

Šunić and

Ventura, The conjugacy problem in automaton groups is not solvable, Journal of Algebra364 (2012), 148–154. doi:10.1016/j.jalgebra.2012.04.014.