{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:35:35Z","timestamp":1759638935585,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,6,27]],"date-time":"2017-06-27T00:00:00Z","timestamp":1498521600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001352","name":"National University of Singapore","doi-asserted-by":"publisher","award":["R146-000-181-112"],"award-info":[{"award-number":["R146-000-181-112"]}],"id":[{"id":"10.13039\/501100001352","id-type":"DOI","asserted-by":"publisher"}]},{"name":"The Marsden Fund of New Zealand","award":["\u2014-"],"award-info":[{"award-number":["\u2014-"]}]},{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["MOE2016-T2-1-019 \/ R146-000-234-112."],"award-info":[{"award-number":["MOE2016-T2-1-019 \/ R146-000-234-112."]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001352","name":"National University of Singapore","doi-asserted-by":"publisher","award":["C252-000-087-001","R252-000-420-112","R252-000-420-112"],"award-info":[{"award-number":["C252-000-087-001","R252-000-420-112","R252-000-420-112"]}],"id":[{"id":"10.13039\/501100001352","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,11]]},"DOI":"10.1007\/s00224-017-9792-7","type":"journal-article","created":{"date-parts":[[2017,6,27]],"date-time":"2017-06-27T00:05:18Z","timestamp":1498521918000},"page":"1254-1287","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Semiautomatic Structures"],"prefix":"10.1007","volume":"61","author":[{"given":"Sanjay","family":"Jain","sequence":"first","affiliation":[]},{"given":"Bakhadyr","family":"Khoussainov","sequence":"additional","affiliation":[]},{"given":"Frank","family":"Stephan","sequence":"additional","affiliation":[]},{"given":"Dan","family":"Teng","sequence":"additional","affiliation":[]},{"given":"Siyuan","family":"Zou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,6,27]]},"reference":[{"key":"9792_CR1","first-page":"96","volume-title":"How the World Computes - Turing Centenary Conference and Eighth Conference on Computability in Europe, CiE 2012, Cambridge, UK, June 18\u201323, 2012. Proceedings. Springer LNCS, vol. 7318","author":"J Case","year":"2012","unstructured":"Case, J., Jain, S., Seah, S., Stephan, F.: Automatic functions, linear time and learning. In: How the World Computes - Turing Centenary Conference and Eighth Conference on Computability in Europe, CiE 2012, Cambridge, UK, June 18\u201323, 2012. Proceedings. Springer LNCS, vol. 7318, pp 96\u2013106 (2012)"},{"key":"9792_CR2","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/BF01746527","volume":"3","author":"A Cobham","year":"1969","unstructured":"Cobham, A.: On the base-dependence of sets of numbers recognizable by finite automata. Mathematical Systems Theory 3, 186\u2013192 (1969)","journal-title":"Mathematical Systems Theory"},{"issue":"1","key":"9792_CR3","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/j.crma.2004.03.035","volume":"339","author":"C Delhomm\u00e9","year":"2004","unstructured":"Delhomm\u00e9, C.: Automaticit\u00e9 des ordinaux et des graphes homog\u00e8nes. Comptes Rendus Mathematique 339(1), 5\u201310 (2004)","journal-title":"Comptes Rendus Mathematique"},{"key":"9792_CR4","doi-asserted-by":"crossref","DOI":"10.1201\/9781439865699","volume-title":"Word Processing in Groups","author":"DBA Epstein","year":"1992","unstructured":"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)"},{"key":"9792_CR5","unstructured":"Fuchs, L.: Partially Ordered Algebraic Systems. Pergamon Press (1963)"},{"key":"9792_CR6","unstructured":"Hodgson, B.R.: Th\u00e9ories d\u00e9cidables par automate fini. Ph.D.Thesis, D\u00e9partement de math\u00e9matiques et de statistique, Universit\u00e9 de Montr\u00e9al (1976)"},{"issue":"1","key":"9792_CR7","first-page":"39","volume":"7","author":"BR Hodgson","year":"1983","unstructured":"Hodgson, B.R.: D\u00e9cidabilit\u00e9 par automate fini. Annales des Sciences Math\u00e9,matiques du Qu\u00e9bec 7(1), 39\u201357 (1983)","journal-title":"Annales des Sciences Math\u00e9,matiques du Qu\u00e9bec"},{"key":"9792_CR8","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/978-3-319-46379-7_13","volume-title":"Algorithmic Learning Theory - Twentyseventh International Conference, ALT 2016, Bari, Italy, October 19\u201321, 2016, Proceedings. Springer LNCS, vol. 9925","author":"R H\u00f6lzl","year":"2016","unstructured":"H\u00f6lzl, R., Jain, S., Stephan, F.: Learning pattern languages over groups. In: Algorithmic Learning Theory - Twentyseventh International Conference, ALT 2016, Bari, Italy, October 19\u201321, 2016, Proceedings. Springer LNCS, vol. 9925, pp 189\u2013203 (2016)"},{"key":"9792_CR9","unstructured":"Hopcroft, J. E., Motwani, R., Ullman, J. D.: Introduction to Automata Theory, Languages and Computation, 3rd edn. Addison Wesley (2007)"},{"key":"9792_CR10","first-page":"204","volume-title":"Computer Science \u2013 Theory and Applications \u2013 Ninth International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7\u201311, 2014. Proceedings. Springer LNCS, vol. 8476","author":"S Jain","year":"2014","unstructured":"Jain, S., Khoussainov, B., Stephan, F., Teng, D., Zou, S.: Semiautomatic structures. In: Computer Science \u2013 Theory and Applications \u2013 Ninth International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7\u201311, 2014. Proceedings. Springer LNCS, vol. 8476, pp 204\u2013217 (2014)"},{"key":"9792_CR11","first-page":"282","volume-title":"Pursuit of the Universal, Twelfth Conference on Computability in Europe, CiE 2016, Paris, France, 27 June\u20131 July 2016, Proceedings. Springer LNCS, vol. 9709","author":"B Khoussainov","year":"2016","unstructured":"Khoussainov, B., Jain, S., Stephan, F.: Finitely generated semiautomatic groups. In: Pursuit of the Universal, Twelfth Conference on Computability in Europe, CiE 2016, Paris, France, 27 June\u20131 July 2016, Proceedings. Springer LNCS, vol. 9709, pp 282\u2013291 (2016)"},{"key":"9792_CR12","unstructured":"Kharlampovich, O., Khoussainov, B., Miasnikov, A.: From automatic structures to automatic groups. arXiv:\n                    1107.3645\n                    \n                   (2011)"},{"key":"9792_CR13","first-page":"367","volume-title":"Logic and Computational Complexity, International Workshop, LCC 1994, Indianapolis, Indiana, USA, October 13\u201316, 1994; Springer LNCS, vol. 960","author":"B Khoussainov","year":"1995","unstructured":"Khoussainov, B., Nerode, A.: Automatic presentations of structures. In: Logic and Computational Complexity, International Workshop, LCC 1994, Indianapolis, Indiana, USA, October 13\u201316, 1994; Springer LNCS, vol. 960, pp 367\u2013392 (1995)"},{"key":"9792_CR14","first-page":"440","volume-title":"Twentyfirst Annual Symposium on Theoretical Aspects of Computer Science, STACS 2004, Montpellier, France, March 25\u201327, 2004, Proceedings; Springer LNCS, vol. 2996","author":"B Khoussainov","year":"2004","unstructured":"Khoussainov, B., Rubin, S., Stephan, F.: Definability and regularity in automatic structures. In: Twentyfirst Annual Symposium on Theoretical Aspects of Computer Science, STACS 2004, Montpellier, France, March 25\u201327, 2004, Proceedings; Springer LNCS, vol. 2996, pp 440\u2013451 (2004)"},{"key":"9792_CR15","doi-asserted-by":"crossref","unstructured":"Kozen, D.: Complexity of Finitely Presented Algebras. PhD thesis, Computer Science Department Cornell University (May 1977)","DOI":"10.1145\/800105.803406"},{"key":"9792_CR16","first-page":"671","volume-title":"Oeuvres de Lagrange, vol. 1","author":"J-L Lagrange","year":"1867","unstructured":"Lagrange, J.-L.: Solution d\u2019un probl\u00e9me d\u2019arithm\u00e9tique. In: Serret, J.-A. (ed.) Oeuvres de Lagrange, vol. 1, pp 671\u2013731 (1867). \n                    http:\/\/gdz.sub.uni-goettingen.de\/no_cache\/dms\/load\/img\/?IDDOC=41029"},{"key":"9792_CR17","first-page":"297","volume":"191","author":"YV Matiyasevich","year":"1970","unstructured":"Matiyasevich, Y.V.: Diofantovost\u2019 perechislimykh mnozhestv. Doklady Akademii Nauk SSSR 191, 297\u2013282 (1970). (Russian). English translation: Enumerable sets are Diophantine, Soviet Mathematics Doklady 11, 354\u2013358 (1970)","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"9792_CR18","volume-title":"Hilbert\u2019s Tenth Problem","author":"YV Matiyasevich","year":"1993","unstructured":"Matiyasevich, Y.V.: Hilbert\u2019s Tenth Problem. MIT Press, Cambridge, Massachusetts (1993)"},{"key":"9792_CR19","first-page":"7183","volume-title":"Language and Automata Theory and Applications - Sixth International Conference, LATA 2012, A Cor\u0169na, Spain, March 5-9, 2012, Proceedings. Springer LNCS, vol. 401\u2013407","author":"A Miasnikov","year":"2012","unstructured":"Miasnikov, A., \u0160uni\u0107, Z.: Cayley graph automatic groups are not necessarily Cayley graph biautomatic. In: Language and Automata Theory and Applications - Sixth International Conference, LATA 2012, A Cor\u0169na, Spain, March 5-9, 2012, Proceedings. Springer LNCS, vol. 401\u2013407, p 7183 (2012)"},{"key":"9792_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/2372087","volume":"71","author":"BH Neumann","year":"1949","unstructured":"Neumann, B.H.: On ordered groups. Am. J. Math. 71, 1\u201318 (1949)","journal-title":"Am. J. Math."},{"issue":"3","key":"9792_CR21","doi-asserted-by":"publisher","first-page":"305","DOI":"10.2178\/bsl\/1186666149","volume":"13","author":"A Nies","year":"2007","unstructured":"Nies, A.: Describing groups. Bull. Symb. Log. 13(3), 305\u2013339 (2007)","journal-title":"Bull. Symb. Log."},{"key":"9792_CR22","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1016\/j.jalgebra.2007.04.015","volume":"320","author":"A Nies","year":"2008","unstructured":"Nies, A., Thomas, R.: FA-Presentable groups and rings. Journal of Algebra 320, 569\u2013585 (2008)","journal-title":"Journal of Algebra"},{"key":"9792_CR23","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1016\/j.apal.2009.07.006","volume":"161","author":"A Nies","year":"2009","unstructured":"Nies, A., Semukhin, P.: Finite automata presentable Abelian groups. Annals of Pure and Applied Logic 161, 458\u2013467 (2009)","journal-title":"Annals of Pure and Applied Logic"},{"key":"9792_CR24","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/BF00967164","volume":"18","author":"AL Semenov","year":"1977","unstructured":"Semenov, A.L.: The Presburger nature of predicates that are regular in two number systems. Sib. Math. J. 18, 289\u2013299 (1977)","journal-title":"Sib. Math. J."},{"key":"9792_CR25","unstructured":"Tan, W.Y.: Automatic Structures. Honours Year Thesis, Department of Mathematics National University of Singapore (2008)"},{"key":"9792_CR26","unstructured":"Teng, D.: Automatic Structures. Honours Year Thesis, Department of Mathematics National University of Singapore (2012)"},{"key":"9792_CR27","unstructured":"Zou, S.: Automatic Semigroups and Ordering. Honours Year Thesis, Department of Mathematics National University of Singapore (2013)"},{"issue":"4","key":"9792_CR28","doi-asserted-by":"publisher","first-page":"1341","DOI":"10.2178\/jsl\/1318338853","volume":"76","author":"T Tsankov","year":"2011","unstructured":"Tsankov, T.: The additive group of the rationals does not have an automatic presentation. J. Symb. Log. 76(4), 1341\u20131351 (2011)","journal-title":"J. Symb. Log."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9792-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9792-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9792-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,3]],"date-time":"2020-03-03T07:07:17Z","timestamp":1583219237000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9792-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,27]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["9792"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9792-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2017,6,27]]},"assertion":[{"value":"27 June 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}