{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T08:01:15Z","timestamp":1761897675699,"version":"3.37.3"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,4,21]],"date-time":"2022-04-21T00:00:00Z","timestamp":1650499200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,21]],"date-time":"2022-04-21T00:00:00Z","timestamp":1650499200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["DI 435\/7-1"],"award-info":[{"award-number":["DI 435\/7-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100009534","name":"Universit\u00e4t Stuttgart","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100009534","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We construct an automaton group with a -complete word problem, proving a conjecture due to Steinberg. Additionally, the constructed group has a provably more difficult, namely -complete, compressed word problem and acts over a binary alphabet. Thus, it is optimal in terms of the alphabet size. Our construction directly simulates the computation of a Turing machine in an automaton group and, therefore, seems to be quite versatile. It combines two ideas: the first one is a construction used by D\u2019Angeli, Rodaro and the first author to obtain an inverse automaton semigroup with a -complete word problem and the second one is to utilize a construction used by Barrington to simulate Boolean circuits of bounded degree and logarithmic depth in the group of even permutations over five elements.<\/jats:p>","DOI":"10.1007\/s00224-021-10064-7","type":"journal-article","created":{"date-parts":[[2022,4,21]],"date-time":"2022-04-21T12:03:02Z","timestamp":1650542582000},"page":"178-218","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["An Automaton Group with PSPACE-Complete Word Problem"],"prefix":"10.1007","volume":"67","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7801-6569","authenticated-orcid":false,"given":"Jan Philipp","family":"W\u00e4chter","sequence":"first","affiliation":[]},{"given":"Armin","family":"Wei\u00df","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,4,21]]},"reference":[{"key":"10064_CR1","unstructured":"Aleshin, S.V.: A free group of finite automata. Vestnik Moskovskogo Universiteta. Seriya I. Matematika, Mekhanika (4), 12\u201314 (1983)"},{"key":"10064_CR2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge (2009)"},{"issue":"1","key":"10064_CR3","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"DA Mix Barrington","year":"1989","unstructured":"Mix Barrington, D.A.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. J. Comput. Syst. Sci. 38(1), 150\u2013164 (1989). https:\/\/doi.org\/10.1016\/0022-0000(89)90037-8","journal-title":"J. Comput. Syst. Sci."},{"key":"10064_CR4","doi-asserted-by":"publisher","unstructured":"Bartholdi, L., Figelius, M., Lohrey, M., Wei\u00df, A.: Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems. In: 35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbr\u00fccken, Germany (Virtual Conference), pp. 29:1\u201329:29. https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2020.29 (2020)","DOI":"10.4230\/LIPIcs.CCC.2020.29"},{"key":"10064_CR5","doi-asserted-by":"publisher","first-page":"705","DOI":"10.4171\/GGD\/560","volume":"14","author":"L Bartholdi","year":"2020","unstructured":"Bartholdi, L., Mitrofanov, I.: The word and order problems for self-similar and automata groups. Groups Geom. Dyn. 14, 705\u2013728 (2020). https:\/\/doi.org\/10.4171\/GGD\/560","journal-title":"Groups Geom. Dyn."},{"key":"10064_CR6","doi-asserted-by":"publisher","DOI":"10.1515\/9783110667028","volume-title":"Complexity and Randomness in Group Theory","author":"F Bassino","year":"2020","unstructured":"Bassino, F., Kapovich, I., Lohrey, M., Miasnikov, A., Nicaud, C., Nikolaev, A., Rivin, I., Shpilrain, V., Ushakov, A., Weil, P.: Complexity and Randomness in Group Theory. De Gruyter, Berlin (2020). https:\/\/doi.org\/10.1515\/9783110667028"},{"key":"10064_CR7","volume-title":"Codes and Automata, Encyclopedia of Mathematics and its Applications, vol. 129","author":"J Berstel","year":"2010","unstructured":"Berstel, J., Perrin, D., Reutenauer, C.: Codes and Automata, Encyclopedia of Mathematics and its Applications, vol. 129. Cambridge University Press, Cambridge (2010)"},{"issue":"2","key":"10064_CR8","doi-asserted-by":"publisher","first-page":"765","DOI":"10.1007\/s00208-011-0757-x","volume":"354","author":"IV Bondarenko","year":"2012","unstructured":"Bondarenko, I.V.: Growth of Schreier graphs of automaton groups. Math. Ann. 354 (2), 765\u2013785 (2012). https:\/\/doi.org\/10.1007\/s00208-011-0757-x","journal-title":"Math. Ann."},{"issue":"2","key":"10064_CR9","first-page":"248","volume":"17","author":"IV Bondarenko","year":"2014","unstructured":"Bondarenko, I.V.: The word problem in Hanoi Towers groups. Algebra Discrete Math. 17(2), 248\u2013255 (2014)","journal-title":"Algebra Discrete Math."},{"issue":"2","key":"10064_CR10","doi-asserted-by":"publisher","first-page":"207","DOI":"10.2307\/1970103","volume":"70","author":"WW Boone","year":"1959","unstructured":"Boone, W.W.: The word problem. Ann. Math. 70(2), 207\u2013265 (1959)","journal-title":"Ann. Math."},{"key":"10064_CR11","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s00233-020-10114-5","volume":"101","author":"D D\u2019Angeli","year":"2020","unstructured":"D\u2019Angeli, D., Rodaro, E., W\u00e4chter, J.Ph.: The structure theory of partial automaton semigroups. Semigroup Forum 101, 51\u201376 (2020). https:\/\/doi.org\/10.1007\/s00233-020-10114-5","journal-title":"Semigroup Forum"},{"key":"10064_CR12","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\u2019Angeli, D., Rodaro, E., W\u00e4chter, J.Ph.: On the complexity of the word problem for automaton semigroups and automaton groups. Adv. Appl. Math. 90, 160\u2013187 (2017). https:\/\/doi.org\/10.1016\/j.aam.2017.05.008","journal-title":"Adv. Appl. Math."},{"key":"10064_CR13","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/BF01456932","volume":"71","author":"M Dehn","year":"1911","unstructured":"Dehn, M.: \u00dcber unendliche diskontinuierliche Gruppen. Math. Ann. 71, 116\u2013144 (1911)","journal-title":"Math. Ann."},{"key":"10064_CR14","unstructured":"Gillibert, P.: Personal Communication (2019)"},{"issue":"01","key":"10064_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1142\/S0218196714500015","volume":"24","author":"P Gillibert","year":"2014","unstructured":"Gillibert, P.: The finiteness problem for automaton semigroups is undecidable. Int. J. Algebra Comput. 24(01), 1\u20139 (2014). https:\/\/doi.org\/10.1142\/S0218196714500015","journal-title":"Int. J. Algebra Comput."},{"key":"10064_CR16","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/j.jalgebra.2017.11.049","volume":"497","author":"P Gillibert","year":"2018","unstructured":"Gillibert, P.: An automaton group with undecidable order and Engel problems. J. Algebra 497, 363\u2013392 (2018). https:\/\/doi.org\/10.1016\/j.jalgebra.2017.11.049","journal-title":"J. Algebra"},{"key":"10064_CR17","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF01078416","volume":"14","author":"RI Grigorchuk","year":"1980","unstructured":"Grigorchuk, R.I.: Burnside\u2019s problem on periodic groups. Funct. Anal. its Appl. 14, 41\u201343 (1980)","journal-title":"Funct. Anal. its Appl."},{"key":"10064_CR18","first-page":"251","volume":"54","author":"RI Grigorchuk","year":"2008","unstructured":"Grigorchuk, R.I., Pak, I.: Groups of intermediate growth: an introduction. L\u2019Enseignement Math\u00e9matique 54, 251\u2013272 (2008)","journal-title":"L\u2019Enseignement Math\u00e9matique"},{"key":"10064_CR19","doi-asserted-by":"crossref","unstructured":"Kozen, D.: Lower bounds for natural proof systems. In: Proc. of the 18th Ann. Symp. on Foundations of Computer Science, FOCS\u201977, pp 254\u2013266. IEEE Computer Society Press, Providence, Rhode Island (1977)","DOI":"10.1109\/SFCS.1977.16"},{"issue":"2","key":"10064_CR20","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/S0019-9958(66)90229-4","volume":"9","author":"K Krohn","year":"1966","unstructured":"Krohn, K., Maurer, W.D., Rhodes, J.L.: Realizing complex boolean functions with simple groups. Inf. Control. 9(2), 190\u2013195 (1966). https:\/\/doi.org\/10.1016\/S0019-9958(66)90229-4","journal-title":"Inf. Control."},{"key":"10064_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-0748-9","volume-title":"The Compressed Word Problem for Groups. Springer Briefs in Mathematics","author":"M Lohrey","year":"2014","unstructured":"Lohrey, M.: The Compressed Word Problem for Groups. Springer Briefs in Mathematics. Springer, Berlin (2014). https:\/\/doi.org\/10.1007\/978-1-4939-0748-9"},{"key":"10064_CR22","first-page":"735","volume":"48","author":"GS Makanin","year":"1984","unstructured":"Makanin, G.S.: Decidability of the universal and positive theories of a free group. Izv. Akad. Nauk SSSR Ser. Mat. 48, 735\u2013749 (1984). Russian; English translation in: Math. USSR Izvestija, 25, 75\u201388, 1985","journal-title":"Izv. Akad. Nauk SSSR Ser. Mat."},{"issue":"5","key":"10064_CR23","first-page":"45","volume":"1","author":"AI Mal\u2019cev","year":"1962","unstructured":"Mal\u2019cev, A.I.: On the equation zxyx\u2212\u20091y\u2212\u20091z\u2212\u20091 = aba\u2212\u20091b\u2212\u20091 in a free group. Akademiya Nauk SSSR. Sibirskoe Otdelenie. Institut Matematiki Algebra i Logika 1(5), 45\u201350 (1962)","journal-title":"Akademiya Nauk SSSR. Sibirskoe Otdelenie. Institut Matematiki Algebra i Logika"},{"issue":"3","key":"10064_CR24","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1090\/S0002-9939-1965-0175971-0","volume":"16","author":"WD Maurer","year":"1965","unstructured":"Maurer, W.D., Rhodes, J.L.: A property of finite simple non-abelian groups. Proc. Am. Math. Soc. 16(3), 552\u2013554 (1965). https:\/\/doi.org\/10.2307\/2034697","journal-title":"Proc. Am. Math. Soc."},{"key":"10064_CR25","doi-asserted-by":"publisher","DOI":"10.1090\/surv\/117","volume-title":"Self-Similar Groups, Mathematical Surveys and Monographs, vol. 117","author":"VV Nekrashevych","year":"2005","unstructured":"Nekrashevych, V.V.: Self-Similar Groups, Mathematical Surveys and Monographs, vol. 117. American Mathematical Society, Providence (2005). https:\/\/doi.org\/10.1090\/surv\/117"},{"key":"10064_CR26","unstructured":"Novikov, P.S.: On the algorithmic unsolvability of the word problem in group theory. Trudy Mat. Inst. Steklov, pp. 1\u2013143. In Russian (1955)"},{"key":"10064_CR27","volume-title":"Computational Complexity","author":"CM Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.M.: Computational Complexity. Addison-Wesley, Boston (1994)"},{"key":"10064_CR28","unstructured":"Robinson, D.: Parallel algorithms for group word problems. Ph.D. thesis, University of California, San Diego (1993)"},{"key":"10064_CR29","doi-asserted-by":"crossref","unstructured":"Stearns, R.E., Hartmanis, J., Lewis, P.M.: Hierarchies of memory limited computations. In: 6th Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 1965), pp. 179\u2013190. IEEE (1965)","DOI":"10.1109\/FOCS.1965.11"},{"key":"10064_CR30","doi-asserted-by":"crossref","unstructured":"Steinberg, B.: On some algorithmic properties of finite state automorphisms of rooted trees. Contemporary Mathematics, vol. 633. American Mathematical Society, Providence (2015)","DOI":"10.1090\/conm\/633\/12655"},{"key":"10064_CR31","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/j.jalgebra.2012.04.014","volume":"364","author":"Z \u0160uni\u0107","year":"2012","unstructured":"\u0160uni\u0107, Z., Ventura, E.: The conjugacy problem in automaton groups is not solvable. J. Algebra 364, 148\u2013154 (2012). https:\/\/doi.org\/10.1016\/j.jalgebra.2012.04.014","journal-title":"J. Algebra"},{"key":"10064_CR32","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s10711-006-9060-5","volume":"124","author":"M Vorobets","year":"2007","unstructured":"Vorobets, M., Vorobets, Y.: On a free group of transformations defined by an automaton. Geom. Dedicata. 124, 237\u2013249 (2007). https:\/\/doi.org\/10.1007\/s10711-006-9060-5","journal-title":"Geom. Dedicata."},{"key":"10064_CR33","doi-asserted-by":"publisher","unstructured":"W\u00e4chter, J. Ph.: Automaton structures \u2013 decision problems and structure theory. Doctoral thesis, Institut f\u00fcr Formale Methoden der Informatik, Universit\u00e4t Stuttgart. https:\/\/doi.org\/10.18419\/opus-11267 (2020)","DOI":"10.18419\/opus-11267"},{"key":"10064_CR34","doi-asserted-by":"publisher","unstructured":"W\u00e4chter, J.Ph., Wei\u00df, A.: An automaton group with PSPACE-complete word problem. In: 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France, pp. 6:1\u20136:17. https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2020.6 (2020)","DOI":"10.4230\/LIPIcs.STACS.2020.6"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-021-10064-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-021-10064-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-021-10064-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,14]],"date-time":"2023-02-14T08:07:14Z","timestamp":1676362034000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-021-10064-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,21]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["10064"],"URL":"https:\/\/doi.org\/10.1007\/s00224-021-10064-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2022,4,21]]},"assertion":[{"value":"24 September 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 April 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}