Abstract
The present work shows that Cayley automatic groups are semiautomatic and exhibits some further constructions of semiautomatic groups and in particular shows that every finitely generated group of nilpotency class 3 is semiautomatic.
S. Jain is supported in part by NUS grants C252-000-087-001, R146-000-181-112 and R146-000-184-112; B. Khoussainov is supported in part by the Marsden Fund grant of the Royal Society of New Zealand; F. Stephan is supported in part by NUS grants R146-000-181-112 and R146-000-184-112.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Berdinsky, D., Khoussainov, B.: On automatic transitive graphs. In: Shur, A.M., Volkov, M.V. (eds.) DLT 2014. LNCS, vol. 8633, pp. 1–12. Springer, Heidelberg (2014)
Case, J., Jain, S., Seah, S., Stephan, F.: Automatic functions, linear time and learning. Logical Meth. Comput. Sci. 9(3), 1–26 (2013)
Epstein, D.B.A., Cannon, J.W., Holt, D.F., Levy, S.V.F., Paterson, M.S., Thurston, W.P.: Word Processing in Groups. Jones and Bartlett Publishers, Boston (1992)
Hodgson, B.R.: Théories décidables par automate fini. Ph.D. thesis, Département de mathématiques et de statistique, Université de Montréal (1976)
Hodgson, B.R.: Décidabilité par automate fini. Annales des sciences mathématiques du Québec 7(1), 39–57 (1983)
Jain, S., Khoussainov, B., Stephan, F., Teng, D., Zou, S.: Semiautomatic structures. In: Hirsch, E.A., Kuznetsov, S.O., Pin, J.É., Vereshchagin, N.K. (eds.) CSR 2014. LNCS, vol. 8476, pp. 204–217. Springer, Heidelberg (2014)
Kharlampovich, O., Khoussainov, B., Miasnikov, A.: From automatic structures to automatic groups. Groups Geom. Dyn. Syst. 8(1), 157–198 (2014)
Khoussainov, B., Nerode, A.: Logic and computational complexity. In: Leivant, D. (ed.) Automatic Presentations of Structures. LNCS, vol. 960, pp. 367–392. Springer, Heidelberg (1995)
Miasnikov, A., Å unić, Z.: Cayley graph automatic groups are not necessarily Cayley graph biautomatic. In: Dediu, A.-H., MartÃn-Vide, C. (eds.) LATA 2012. LNCS, vol. 7183, pp. 401–407. Springer, Heidelberg (2012)
Nies, A.: Describing groups. Bull. Symbolic Logic 13(3), 305–339 (2007)
Nies, A., Thomas, R.: FA-presentable groups and rings. J. Algebra 320, 569–585 (2008)
Šunić, Z., Ventura, E.: The conjugacy problem in automaton groups is not solvable. J. Algebra 364, 148–154 (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Jain, S., Khoussainov, B., Stephan, F. (2016). Finitely Generated Semiautomatic Groups. In: Beckmann, A., Bienvenu, L., Jonoska, N. (eds) Pursuit of the Universal. CiE 2016. Lecture Notes in Computer Science(), vol 9709. Springer, Cham. https://doi.org/10.1007/978-3-319-40189-8_29
Download citation
DOI: https://doi.org/10.1007/978-3-319-40189-8_29
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-40188-1
Online ISBN: 978-3-319-40189-8
eBook Packages: Computer ScienceComputer Science (R0)