{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T00:49:00Z","timestamp":1767142140969,"version":"build-2238731810"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,2,12]],"date-time":"2020-02-12T00:00:00Z","timestamp":1581465600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,12]],"date-time":"2020-02-12T00:00:00Z","timestamp":1581465600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Isr. J. Math."],"published-print":{"date-parts":[[2020,6]]},"DOI":"10.1007\/s11856-020-1972-5","type":"journal-article","created":{"date-parts":[[2020,2,12]],"date-time":"2020-02-12T04:02:47Z","timestamp":1581480167000},"page":"15-52","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Automaton semigroups and groups: On the undecidability of problems related to freeness and finiteness"],"prefix":"10.1007","volume":"237","author":[{"given":"Daniele","family":"D\u2019Angeli","sequence":"first","affiliation":[]},{"given":"Emanuele","family":"Rodaro","sequence":"additional","affiliation":[]},{"given":"Jan Philipp","family":"W\u00e4chter","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,12]]},"reference":[{"key":"1972_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1142\/S021819671250052X","volume":"22","author":"A Akhavi","year":"2012","unstructured":"A. Akhavi, I. Klimann, S. Lombardy, J. Mairesse and M. Picantin, On the finiteness problem for automaton (semi)groups, International Journal of Algebra and Computation 22 (2012), 1\u201326.","journal-title":"International Journal of Algebra and Computation"},{"key":"1972_CR2","unstructured":"L. Bartholdi and I. Mitrofanov, The word and order problems for self-similar and automata groups, https:\/\/arxiv.org\/abs\/1710.10109."},{"key":"1972_CR3","doi-asserted-by":"publisher","first-page":"3157","DOI":"10.1090\/tran\/6963","volume":"369","author":"J Belk","year":"2017","unstructured":"J. Belk and C. Bleak, Some undecidability results for asynchronous transducers and the Brin-Thompson group 2V, Transactions of the American Mathematical Society 369 (2017), 3157\u20133172.","journal-title":"Transactions of the American Mathematical Society"},{"key":"1972_CR4","doi-asserted-by":"publisher","first-page":"963","DOI":"10.1142\/S0129054110007660","volume":"21","author":"P C Bell","year":"2010","unstructured":"P. C. Bell and I. Potapov, On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups, International Journal of Foundations of Computer Science 21 (2010), 963\u2013978.","journal-title":"International Journal of Foundations of Computer Science"},{"key":"1972_CR5","doi-asserted-by":"publisher","first-page":"323","DOI":"10.4171\/GGD\/184","volume":"7","author":"I V Bondarenko","year":"2013","unstructured":"I. V. Bondarenko, N. Bondarenko, S. Sidki and F. Zapata, On the conjugacy problem for finite-state automorphisms of regular rooted trees, Groups, Geometry, and Dynamics 7 (2013), 323\u2013355.","journal-title":"Groups, Geometry, and Dynamics"},{"key":"1972_CR6","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1007\/s00233-014-9632-x","volume":"90","author":"T Brough","year":"2015","unstructured":"T. Brough and A. J. Cain, Automaton semigroup constructions, Semigroup Forum 90 (2015), 763\u2013774.","journal-title":"Semigroup Forum"},{"key":"1972_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2017.02.003","volume":"674","author":"T Brough","year":"2017","unstructured":"T. Brough and A. J. Cain, Automaton semigroups: new constructions results and examples of non-automaton semigroups, Theoretical Computer Science 674 (2017), 1\u201315.","journal-title":"Theoretical Computer Science"},{"key":"1972_CR8","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1142\/S0218196798000077","volume":"08","author":"A M Brunner","year":"1998","unstructured":"A. M. Brunner and S. Sidki, The generation of GL(n, Z) by finite state automata, International Journal of Algebra and Computation 08 (1998), 127\u2013139.","journal-title":"International Journal of Algebra and Computation"},{"key":"1972_CR9","doi-asserted-by":"publisher","first-page":"5022","DOI":"10.1016\/j.tcs.2009.07.054","volume":"410","author":"A J Cain","year":"2009","unstructured":"A. J. Cain, Automaton semigroups, Theoretical Computer Science 410 (2009), 5022\u20135038.","journal-title":"Theoretical Computer Science"},{"key":"1972_CR10","doi-asserted-by":"publisher","first-page":"167","DOI":"10.3934\/jmd.2010.4.167","volume":"4","author":"D D\u2019Angeli","year":"2010","unstructured":"D. D\u2019Angeli, A. Donno, M. Matter and T. Nagnibeda, Schreier graphs of the Basilica group, Journal of Modern Dynamics 4 (2010), 167\u2013205.","journal-title":"Journal of Modern Dynamics"},{"key":"1972_CR11","unstructured":"D. D\u2019Angeli, D. Francoeur, E. Rodaro and J. Ph. W\u00e4chter, Orbits of automaton semigroups and groups, https:\/\/arxiv.org\/abs\/1903.00222."},{"key":"1972_CR12","unstructured":"D. D\u2019Angeli, Th. Godin, I. Klimann, M. Picantin and E. Rodaro, Boundary action of automaton groups without singular points and Wang tilings, https:\/\/arxiv.org\/abs\/1604.07736."},{"key":"1972_CR13","doi-asserted-by":"publisher","first-page":"773","DOI":"10.1142\/S0218196714500337","volume":"24","author":"D D\u2019Angeli","year":"2014","unstructured":"D. D\u2019Angeli and E. Rodaro, Groups and semigroups defined by colorings of synchronizing automata, International Journal of Algebra and Computation 24 (2014), 773\u2013793.","journal-title":"International Journal of Algebra and Computation"},{"key":"1972_CR14","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s10711-014-0024-x","volume":"174","author":"D D\u2019Angeli","year":"2015","unstructured":"D. D\u2019Angeli and E. Rodaro, A geometric approach to (semi)-groups defined by automata via dual transducers, Geometriae Dedicata 174 (2015), 375\u2013400.","journal-title":"Geometriae Dedicata"},{"key":"1972_CR15","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.jalgebra.2016.05.015","volume":"462","author":"D D\u2019Angeli","year":"2016","unstructured":"D. D\u2019Angeli and E. Rodaro, Freeness of automaton groups vs boundary dynamics, Journal of Algebra 462 (2016) 115\u2013136.","journal-title":"Journal of Algebra"},{"key":"1972_CR16","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1016\/j.aam.2017.05.008","volume":"90","author":"D D\u2019Angeli","year":"2017","unstructured":"D. D\u2019Angeli, E. Rodaro and J. Ph. W\u00e4chter, On the complexity of the word problem for automaton semigroups and automaton groups, Advances in Applied Mathematics 90 (2017) 160\u2013187.","journal-title":"Advances in Applied Mathematics"},{"key":"1972_CR17","unstructured":"D. D\u2019Angeli, E. Rodaro and J. Ph. W\u00e4chter, On the structure theory of partial automaton semigroups, https:\/\/arxiv.org\/abs\/1811.09420."},{"key":"1972_CR18","unstructured":"D. Francoeur, Infinite finitely generated atomata semigroups have infinite orbits, https:\/\/arxiv.org\/abs\/1801.10009."},{"key":"1972_CR19","unstructured":"D. Francoeur and I. Mitrofanov, On the existence of free subsemigroups in reversible automata semigroups, https:\/\/arxiv.org\/abs\/1811.04679."},{"key":"1972_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1142\/S0218196714500015","volume":"24","author":"P Gillibert","year":"2014","unstructured":"P. Gillibert, The finiteness problem for automaton semigroups is undecidable, International Journal of Algebra and Computation 24 (2014) 1\u20139.","journal-title":"International Journal of Algebra and Computation"},{"key":"1972_CR21","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/j.jalgebra.2017.11.049","volume":"497","author":"P Gillibert","year":"2018","unstructured":"P. Gillibert, An automaton group with undecidable order and Engel problems, Journal of Algebra 497 (2018) 363\u2013392.","journal-title":"Journal of Algebra"},{"key":"1972_CR22","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1007\/978-3-319-15579-1_25","volume":"8977","author":"Th Godin","year":"2015","unstructured":"Th. Godin, I. Klimann and M. Picantin, On torsion-free semigroups generated by invertible reversible Mealy automata, in Language and Automata Theory and Applications (LATA 2015), Lecture Notes in Computer Science, Vol. 8977, Springer, Berlin, 2015, pp. 328\u2013339.","journal-title":"Language and Automata Theory and Applications (LATA 2015)"},{"key":"1972_CR23","first-page":"128","volume":"231","author":"R I Grigorchuk","year":"2000","unstructured":"R. I. Grigorchuk, V. V. Nekrashevych and V. I. Sushchansky, Automata, dynamical systems, and groups, Proceedings of the Steklov Institute of Mathematics 231 (2000) 128\u2013203.","journal-title":"Proceedings of the Steklov Institute of Mathematics"},{"key":"1972_CR24","volume-title":"Metric Structures for Riemannian and Non-Riemannian Spaces","author":"M Gromov","year":"2007","unstructured":"M. Gromov, Metric Structures for Riemannian and Non-Riemannian Spaces, Modern Birkh\u00e4user Classics, Birkh\u00e4user, Boston, MA, 2007."},{"key":"1972_CR25","unstructured":"J. M. Howie, Fundamentals of Semigroup Theory, London Mathematical Society Monographs, Vol. 12, Clarendon Press, Oxford University Press, New York, 1995."},{"key":"1972_CR26","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/s000390050090","volume":"9","author":"J Kari","year":"1999","unstructured":"J. Kari and P. Papasoglu, Deterministic aperiodic tile sets, Geometric and Functional Analysis 9 (1999) 353\u2013369.","journal-title":"Geometric and Functional Analysis"},{"key":"1972_CR27","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1142\/S0218196791000146","volume":"1","author":"D A Klarner","year":"1991","unstructured":"D. A. Klarner, J.-C. Birget and W. Satterfield, On the undecidability of the freeness of integer matrix semigroups, International Journal of Algebra and Computation 1 (1991) 223\u2013226.","journal-title":"International Journal of Algebra and Computation"},{"key":"1972_CR28","first-page":"502","volume":"20","author":"I Klimann","year":"2013","unstructured":"I. Klimann, The finiteness of a group generated by a 2-letter invertible-reversible mealy automaton is decidable, in 30th International Symposium on Theoretical Aspects of Computer Science, Leibniz International Proceedings in Informatics, Vol. 20, Schloss Dagstuhl-Leibniz Center for Informatics, Wadern, 2013, pp. 502\u2013513.","journal-title":"30th International Symposium on Theoretical Aspects of Computer Science"},{"key":"1972_CR29","unstructured":"M. Lothaire, Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Vol. 17, Addison-Wesley, Reading, MA, 1983."},{"key":"1972_CR30","doi-asserted-by":"publisher","first-page":"1516","DOI":"10.1016\/j.tcs.2008.12.006","volume":"410","author":"V Lukkarila","year":"2009","unstructured":"V. Lukkarila, The 4-way deterministic tiling problem is undecidable, Theoretical Computer Science 410 (2009), 1516\u20131533.","journal-title":"Theoretical Computer Science"},{"key":"1972_CR31","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1142\/S0218196706003153","volume":"16","author":"V V Nekrashevych","year":"2006","unstructured":"V. V. Nekrashevych, Self-similar inverse semigroups and Smale spaces, International Journal of Algebra and Computation 16 (2006), 849\u2013874.","journal-title":"International Journal of Algebra and Computation"},{"key":"1972_CR32","doi-asserted-by":"publisher","first-page":"923","DOI":"10.1142\/S0218196710005960","volume":"20","author":"A S Olijnyk","year":"2010","unstructured":"A. S. Olijnyk, V. I. Sushchansky and J. K. S\u0142upik, Inverse semigroups of partial automaton permutations, International Journal of Algebra and Computation 20 (2010), 923\u2013952.","journal-title":"International Journal of Algebra and Computation"},{"key":"1972_CR33","unstructured":"F. Olukoya, The growth rates of automaton groups generated by reset automata, https:\/\/arxiv.org\/abs\/1708.07209."},{"key":"1972_CR34","volume-title":"Pure and Applied Mathematics","author":"M Petrich","year":"1984","unstructured":"M. Petrich, Inverse Semigroups, Pure and Applied Mathematics, John Wiley & Sons, New York, 1984."},{"key":"1972_CR35","volume-title":"Decision problems on iterated length-preserving transducers","author":"A Pierce","year":"2011","unstructured":"A. Pierce, Decision problems on iterated length-preserving transducers, Senior Thesis, Carnegie Mellon University, 2011."},{"key":"1972_CR36","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/BF01418780","volume":"12","author":"R M Robinson","year":"1971","unstructured":"R. M. Robinson, Undecidability and nonperiodicity for tilings of the plane, Inventiones mathematicae 12 (1971), 177\u2013209.","journal-title":"Inventiones mathematicae"},{"key":"1972_CR37","doi-asserted-by":"publisher","first-page":"1213","DOI":"10.1142\/S0218196705002761","volume":"15","author":"P V Silva","year":"2005","unstructured":"P. V. Silva and B. Steinberg, On a class of automata groups generalizing lamplighter groups, International Journal of Algebra and Computation 15 (2005), 1213\u20131234.","journal-title":"International Journal of Algebra and Computation"},{"key":"1972_CR38","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/j.jalgebra.2012.04.014","volume":"364","author":"Z \u0160uni\u0107","year":"2012","unstructured":"Z. \u0160uni\u0107 and E. Ventura, The conjugacy problem in automaton groups is not solvable, Journal of Algebra 364 (2012), 148\u2013154.","journal-title":"Journal of Algebra"},{"key":"1972_CR39","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1090\/conm\/567\/11250","volume":"567","author":"Y Vorobets","year":"2012","unstructured":"Y. Vorobets, Notes on the Schreier graphs of the Grigorchuk group, in Dynamical Systems and Group Actions, Contemporary Mathematics, Vol. 567, American Mathematical Society, Providence, RI, 2012, pp. 221\u2013248.","journal-title":"Dynamical Systems and Group Actions"},{"key":"1972_CR40","unstructured":"J. Ph. W\u00e4chter and A. Wei\u00df, An automaton group with PSpace-complete word problem, https:\/\/arxiv.org\/abs\/1906.03424."},{"key":"1972_CR41","first-page":"165","volume":"16","author":"A Zuk","year":"2012","unstructured":"A. Zuk, Automata groups, in Topics in Noncommutative Geometry, Clay Mathematics Proceedings, Vol. 16, American Mathematical Society, Providence, RI, 2012, pp. 165\u2013196.","journal-title":"Topics in Noncommutative Geometry"}],"updated-by":[{"DOI":"10.1007\/s11856-021-2206-1","type":"erratum","label":"Erratum","source":"publisher","updated":{"date-parts":[[2021,10,6]],"date-time":"2021-10-06T00:00:00Z","timestamp":1633478400000}}],"container-title":["Israel Journal of Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11856-020-1972-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11856-020-1972-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11856-020-1972-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,26]],"date-time":"2023-09-26T15:06:09Z","timestamp":1695740769000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11856-020-1972-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,12]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["1972"],"URL":"https:\/\/doi.org\/10.1007\/s11856-020-1972-5","relation":{},"ISSN":["0021-2172","1565-8511"],"issn-type":[{"value":"0021-2172","type":"print"},{"value":"1565-8511","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,12]]},"assertion":[{"value":"20 December 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 April 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 February 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 October 2021","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Erratum","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"An Erratum to this paper has been published:","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s11856-021-2206-1","URL":"https:\/\/doi.org\/10.1007\/s11856-021-2206-1","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}