An automaton group with PSPACE-complete word problem. (English) Zbl 07680323
Summary: We construct an automaton group with a PSPACE-complete word problem, proving a conjecture due to Steinberg. Additionally, the constructed group has a provably more difficult, namely EXPSPACE-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’Angeli, Rodaro and the first author to obtain an inverse automaton semigroup with a PSPACE-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.
MSC:
| 68Qxx | Theory of computing |
| 20Fxx | Special aspects of infinite or finite groups |
| 20Exx | Structure and classification of infinite or finite groups |
References:
| [1] | Aleshin, S.V.: A free group of finite automata. Vestnik Moskovskogo Universiteta. Seriya I. Matematika, Mekhanika (4), 12-14 (1983) · Zbl 0513.68044 |
| [2] | Arora, S.; Barak, B., Computational Complexity: A Modern Approach (2009), Cambridge: Cambridge University Press, Cambridge · Zbl 1193.68112 · doi:10.1017/CBO9780511804090 |
| [3] | Mix Barrington, DA, Bounded-width polynomial-size branching programs recognize exactly those languages in NC1, J. Comput. Syst. Sci., 38, 1, 150-164 (1989) · Zbl 0667.68059 · doi:10.1016/0022-0000(89)90037-8 |
| [4] | Bartholdi, L., Figelius, M., Lohrey, M., Weiß, 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ücken, Germany (Virtual Conference), pp. 29:1-29:29. doi:10.4230/LIPIcs.CCC.2020.29 (2020) · Zbl 07561757 |
| [5] | Bartholdi, L.; Mitrofanov, I., The word and order problems for self-similar and automata groups, Groups Geom. Dyn., 14, 705-728 (2020) · Zbl 1496.20056 · doi:10.4171/GGD/560 |
| [6] | 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 (2020), Berlin: De Gruyter, Berlin · Zbl 1515.20003 · doi:10.1515/9783110667028 |
| [7] | Berstel, J.; Perrin, D.; Reutenauer, C., Codes and Automata, Encyclopedia of Mathematics and its Applications, vol. 129 (2010), Cambridge: Cambridge University Press, Cambridge · Zbl 1187.94001 |
| [8] | Bondarenko, IV, Growth of Schreier graphs of automaton groups, Math. Ann., 354, 2, 765-785 (2012) · Zbl 1280.20042 · doi:10.1007/s00208-011-0757-x |
| [9] | Bondarenko, IV, The word problem in Hanoi Towers groups, Algebra Discrete Math., 17, 2, 248-255 (2014) · Zbl 1328.20053 |
| [10] | Boone, WW, The word problem, Ann. Math., 70, 2, 207-265 (1959) · Zbl 0102.00902 · doi:10.2307/1970103 |
| [11] | D’Angeli, D.; Rodaro, E.; Wächter, JPh, The structure theory of partial automaton semigroups, Semigroup Forum, 101, 51-76 (2020) · Zbl 1508.20126 · doi:10.1007/s00233-020-10114-5 |
| [12] | D’Angeli, D.; Rodaro, E.; Wächter, JPh, On the complexity of the word problem for automaton semigroups and automaton groups, Adv. Appl. Math., 90, 160-187 (2017) · Zbl 1393.20014 · doi:10.1016/j.aam.2017.05.008 |
| [13] | Dehn, M., Über unendliche diskontinuierliche Gruppen, Math. Ann., 71, 116-144 (1911) · JFM 42.0508.03 · doi:10.1007/BF01456932 |
| [14] | Gillibert, P.: Personal Communication (2019) |
| [15] | Gillibert, P., The finiteness problem for automaton semigroups is undecidable, Int. J. Algebra Comput., 24, 1, 1-9 (2014) · Zbl 1292.20040 · doi:10.1142/S0218196714500015 |
| [16] | Gillibert, P., An automaton group with undecidable order and Engel problems, J. Algebra, 497, 363-392 (2018) · Zbl 1427.20040 · doi:10.1016/j.jalgebra.2017.11.049 |
| [17] | Grigorchuk, RI, Burnside’s problem on periodic groups, Funct. Anal. its Appl., 14, 41-43 (1980) · Zbl 0595.20029 · doi:10.1007/BF01078416 |
| [18] | Grigorchuk, RI; Pak, I., Groups of intermediate growth: an introduction, L’Enseignement Mathématique, 54, 251-272 (2008) · Zbl 1204.20049 |
| [19] | Kozen, D.: Lower bounds for natural proof systems. In: Proc. of the 18th Ann. Symp. on Foundations of Computer Science, FOCS’77, pp 254-266. IEEE Computer Society Press, Providence, Rhode Island (1977) |
| [20] | Krohn, K.; Maurer, WD; Rhodes, JL, Realizing complex boolean functions with simple groups, Inf. Control., 9, 2, 190-195 (1966) · Zbl 0202.31502 · doi:10.1016/S0019-9958(66)90229-4 |
| [21] | Lohrey, M., The Compressed Word Problem for Groups. Springer Briefs in Mathematics (2014), Berlin: Springer, Berlin · Zbl 1391.20003 · doi:10.1007/978-1-4939-0748-9 |
| [22] | Makanin, GS, Decidability of the universal and positive theories of a free group, Izv. Akad. Nauk SSSR Ser. Mat., 48, 735-749 (1984) |
| [23] | Mal’cev, AI, On the equation zxyx− 1y − 1z − 1 = aba− 1b − 1 in a free group, Akademiya Nauk SSSR. Sibirskoe Otdelenie. Institut Matematiki Algebra i Logika, 1, 5, 45-50 (1962) · Zbl 0144.01403 |
| [24] | Maurer, WD; Rhodes, JL, A property of finite simple non-abelian groups, Proc. Am. Math. Soc., 16, 3, 552-554 (1965) · Zbl 0132.26903 · doi:10.1090/S0002-9939-1965-0175971-0 |
| [25] | Nekrashevych, VV, Self-Similar Groups, Mathematical Surveys and Monographs, vol. 117 (2005), Providence: American Mathematical Society, Providence · Zbl 1087.20032 |
| [26] | Novikov, P.S.: On the algorithmic unsolvability of the word problem in group theory. Trudy Mat. Inst. Steklov, pp. 1-143. In Russian (1955) |
| [27] | Papadimitriou, CM, Computational Complexity (1994), Boston: Addison-Wesley, Boston · Zbl 0833.68049 |
| [28] | Robinson, D.: Parallel algorithms for group word problems. Ph.D. thesis, University of California, San Diego (1993) |
| [29] | 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-190. IEEE (1965) · Zbl 0229.02033 |
| [30] | Steinberg, B.: On some algorithmic properties of finite state automorphisms of rooted trees. Contemporary Mathematics, vol. 633. American Mathematical Society, Providence (2015) · Zbl 1326.20037 |
| [31] | Šunić, Z.; Ventura, E., The conjugacy problem in automaton groups is not solvable, J. Algebra, 364, 148-154 (2012) · Zbl 1261.20034 · doi:10.1016/j.jalgebra.2012.04.014 |
| [32] | Vorobets, M.; Vorobets, Y., On a free group of transformations defined by an automaton, Geom. Dedicata., 124, 237-249 (2007) · Zbl 1183.20024 · doi:10.1007/s10711-006-9060-5 |
| [33] | Wächter, J. Ph.: Automaton structures – decision problems and structure theory. Doctoral thesis, Institut für Formale Methoden der Informatik, Universität Stuttgart. doi:10.18419/opus-11267 (2020) |
| [34] | Wächter, J.Ph., Weiß, 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-6:17. doi:10.4230/LIPIcs.STACS.2020.6 (2020) · Zbl 07650891 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
