{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T10:39:58Z","timestamp":1783075198632,"version":"3.54.6"},"reference-count":64,"publisher":"Association for Computing Machinery (ACM)","issue":"3-4","license":[{"start":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T00:00:00Z","timestamp":1672444800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DFG","award":["LO 748\/12-1, LO 748\/12-1, DI 435\/7-1 and WE 6835\/1-2"],"award-info":[{"award-number":["LO 748\/12-1, LO 748\/12-1, DI 435\/7-1 and WE 6835\/1-2"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>\n            We give lower bounds on the complexity of the word problem for a large class of non-solvable infinite groups that we call strongly efficiently non-solvable groups. This class includes free groups, Grigorchuk\u2019s group, and Thompson\u2019s groups. We prove that these groups have an NC\n            <jats:sup>1<\/jats:sup>\n            -hard word problem and that for some of them (including Grigorchuk\u2019s group and Thompson\u2019s groups) the compressed word problem (which is equivalent to the circuit evaluation problem) is PSPACE-complete.\n          <\/jats:p>","DOI":"10.1145\/3569708","type":"journal-article","created":{"date-parts":[[2022,12,1]],"date-time":"2022-12-01T12:37:58Z","timestamp":1669898278000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Groups with ALOGTIME-hard Word Problems and PSPACE-complete Compressed Word Problems"],"prefix":"10.1145","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1243-6384","authenticated-orcid":false,"given":"Laurent","family":"Bartholdi","sequence":"first","affiliation":[{"name":"Saarland University, Saarbr\u00fccken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0407-0597","authenticated-orcid":false,"given":"Michael","family":"Figelius","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Siegen, Siegen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4680-7198","authenticated-orcid":false,"given":"Markus","family":"Lohrey","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Siegen, Siegen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7645-5867","authenticated-orcid":false,"given":"Armin","family":"Wei\u00df","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Stuttgart, Stuttgart, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,2]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1112\/S002460930500425X"},{"key":"e_1_3_2_3_2","first-page":"1045","article-title":"The virtual Haken conjecture","volume":"18","author":"Agol Ian","year":"2013","unstructured":"Ian Agol. 2013. The virtual Haken conjecture. Doc. Math. 18 (2013), 1045\u20131087.","journal-title":"Doc. Math."},{"key":"e_1_3_2_4_2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity\u2014A Modern Approach","author":"Arora Sanjeev","year":"2009","unstructured":"Sanjeev Arora and Boaz Barak. 2009. Computational Complexity\u2014A Modern Approach. Cambridge University Press."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90037-8"},{"key":"e_1_3_2_6_2","doi-asserted-by":"crossref","first-page":"941","DOI":"10.1145\/48014.63138","article-title":"Finite monoids and the fine structure of  \\(NC^{1}\\)","volume":"35","author":"Barrington David A. Mix","year":"1988","unstructured":"David A. Mix Barrington and Denis Th\u00e9rien. 1988. Finite monoids and the fine structure of \\(NC^{1}\\) . J. ACM 35 (1988), 941\u2013952.","journal-title":"J. ACM"},{"key":"e_1_3_2_7_2","series-title":"Proceedings of the 35th Computational Complexity Conference (CCC\u201920),","first-page":"29:1\u201329:29","volume":"169","author":"Bartholdi Laurent","year":"2020","unstructured":"Laurent Bartholdi, Michael Figelius, Markus Lohrey, and Armin Wei\u00df. 2020. Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems. In Proceedings of the 35th Computational Complexity Conference (CCC\u201920),LIPIcs, Vol. 169, Shubhangi Saraf (Ed.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 29:1\u201329:29. DOI:10.4230\/LIPIcs.CCC.2020.29"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-7954(03)80078-5"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.4171\/GGD\/42"},{"issue":"1","key":"e_1_3_2_10_2","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1137\/S0097539793249530","article-title":"Finite Monoids: From word to circuit evaluation","volume":"26","author":"Beaudry Martin","year":"1997","unstructured":"Martin Beaudry, Pierre McKenzie, Pierre P\u00e9ladeau, and Denis Th\u00e9rien. 1997. Finite Monoids: From word to circuit evaluation. SIAM J. Comput. 26, 1 (1997), 138\u2013152.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90084-S"},{"issue":"2","key":"e_1_3_2_12_2","doi-asserted-by":"crossref","first-page":"207","DOI":"10.2307\/1970103","article-title":"The word problem","volume":"70","author":"Boone William W.","year":"1959","unstructured":"William W. Boone. 1959. The word problem. Ann. Math. 70, 2 (1959), 207\u2013265.","journal-title":"Ann. Math."},{"issue":"2","key":"e_1_3_2_13_2","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0304-3975(92)90125-Y","article-title":"A uniform approach to define complexity classes","volume":"104","author":"Bovet Daniel P.","year":"1992","unstructured":"Daniel P. Bovet, Pierluigi Crescenzi, and Riccardo Silvestri. 1992. A uniform approach to define complexity classes. Theor. Comput. Sci. 104, 2 (1992), 263\u2013283.","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"e_1_3_2_14_2","first-page":"215","article-title":"Introductory notes on Richard Thompson\u2019s groups","volume":"42","author":"Cannon John W.","year":"1996","unstructured":"John W. Cannon, William J. Floyd, and Walter R. Parry. 1996. Introductory notes on Richard Thompson\u2019s groups. L\u2019Enseign. Math. 42, 3 (1996), 215\u2013256.","journal-title":"L\u2019Enseign. Math."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1588"},{"issue":"7","key":"e_1_3_2_16_2","doi-asserted-by":"crossref","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","article-title":"The smallest grammar problem","volume":"51","author":"Charikar Moses","year":"2005","unstructured":"Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, Amit Sahai, and Abhi Shelat. 2005. The smallest grammar problem. IEEE Trans. Inf. Theory 51, 7 (2005), 2554\u20132576.","journal-title":"IEEE Trans. Inf. Theory"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01456932"},{"key":"e_1_3_2_18_2","first-page":"126:1\u2013126:18","volume-title":"Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP\u201920)","author":"Figelius Michael","year":"2020","unstructured":"Michael Figelius, Moses Ganardi, Markus Lohrey, and Georg Zetzsche. 2020. The complexity of knapsack problems in wreath products. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP\u201920). 126:1\u2013126:18. DOI:10.4230\/LIPIcs.ICALP.2020.126"},{"issue":"1","key":"e_1_3_2_19_2","first-page":"1:1\u20131:25","article-title":"A universal tree balancing theorem","volume":"11","author":"Ganardi Moses","year":"2019","unstructured":"Moses Ganardi and Markus Lohrey. 2019. A universal tree balancing theorem. ACM Trans. Comput. Theory 11, 1 (2019), 1:1\u20131:25.","journal-title":"ACM Trans. Comput. Theory"},{"key":"e_1_3_2_20_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman."},{"issue":"1","key":"e_1_3_2_21_2","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0304-3975(91)90074-C","article-title":"The complexity of Grigorchuk groups with application to cryptography","volume":"88","author":"Garzon Max","year":"1991","unstructured":"Max Garzon and Yechezkel Zalcstein. 1991. The complexity of Grigorchuk groups with application to cryptography. Theor. Comput. Sci. 88, 1 (1991), 83\u201398.","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"e_1_3_2_22_2","first-page":"53","article-title":"On Burnside\u2019s problem on periodic groups","volume":"14","author":"Grigorchuk Rostislav I.","year":"1980","unstructured":"Rostislav I. Grigorchuk. 1980. On Burnside\u2019s problem on periodic groups. Funkts. Anal. Prilozhen. 14, 1 (1980), 53\u201354.","journal-title":"Funkts. Anal. Prilozhen."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.crma.2006.02.001"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1070\/SM1999v190n08ABEH000419"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01179757"},{"issue":"5","key":"e_1_3_2_26_2","doi-asserted-by":"crossref","first-page":"1890","DOI":"10.1016\/j.aim.2010.01.011","article-title":"Coxeter groups are virtually special","volume":"224","author":"Haglund Fr\u00e9d\u00e9ric","year":"2010","unstructured":"Fr\u00e9d\u00e9ric Haglund and Daniel T. Wise. 2010. Coxeter groups are virtually special. Adv. Math. 224, 5 (2010), 1890\u20131903.","journal-title":"Adv. Math."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90081-R"},{"key":"e_1_3_2_28_2","volume-title":"\u00dcber Komplexit\u00e4tsklassen, die mit Hilfe von k-wertigen Funktionen definiert werden.","author":"Hertrampf Ulrich","year":"1994","unstructured":"Ulrich Hertrampf. 1994. \u00dcber Komplexit\u00e4tsklassen, die mit Hilfe von k-wertigen Funktionen definiert werden. Habilitationsschrift. Universit\u00e4t W\u00fcrzburg."},{"key":"e_1_3_2_29_2","series-title":"Proceedings of the 3rd Annual International Conference on Computing and Combinatorics (COCOON\u201997)","first-page":"412","volume":"1276","author":"Hertrampf Ulrich","year":"1997","unstructured":"Ulrich Hertrampf. 1997. The shapes of trees. In Proceedings of the 3rd Annual International Conference on Computing and Combinatorics (COCOON\u201997), Lecture Notes in Computer Science, Vol. 1276. Springer, 412\u2013421."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/348210.348215"},{"key":"e_1_3_2_31_2","first-page":"200","volume-title":"Proceedings of the 8th Annual Structure in Complexity Theory Conference","author":"Hertrampf Ulrich","year":"1993","unstructured":"Ulrich Hertrampf, Clemens Lautemann, Thomas Schwentick, Heribert Vollmer, and Klaus W. Wagner. 1993. On the power of polynomial time bit-reductions. In Proceedings of the 8th Annual Structure in Complexity Theory Conference. IEEE Computer Society Press, 200\u2013207."},{"issue":"4","key":"e_1_3_2_32_2","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1007\/BF01192696","article-title":"On balanced versus unbalanced computation trees","volume":"29","author":"Hertrampf Ulrich","year":"1996","unstructured":"Ulrich Hertrampf, Heribert Vollmer, and Klaus Wagner. 1996. On balanced versus unbalanced computation trees. Math. Syst. Theory 29, 4 (1996), 411\u2013421.","journal-title":"Math. Syst. Theory"},{"key":"e_1_3_2_33_2","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1109\/SFCS.1994.365729","volume-title":"Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS\u201994)","author":"Hirshfeld Yoram","year":"1994","unstructured":"Yoram Hirshfeld, Mark Jerrum, and Faron Moller. 1994. A polynomial-time algorithm for deciding equivalence of normed context-free processes. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS\u201994). IEEE Computer Society, 623\u2013631. DOI:10.1109\/SFCS.1994.365729"},{"key":"e_1_3_2_34_2","doi-asserted-by":"crossref","unstructured":"Derek Holt and Sarah Rees. 2020. The compressed word problem in relatively hyperbolic groups. Journal of Algebra 607 (2022) 305\u2013343. 10.1016\/j.jalgebra.2022.01.001","DOI":"10.1016\/j.jalgebra.2022.01.001"},{"key":"e_1_3_2_35_2","series-title":"Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS\u201919),","first-page":"37:1\u201337:16","volume":"126","author":"Holt Derek F.","year":"2019","unstructured":"Derek F. Holt, Markus Lohrey, and Saul Schleimer. 2019. Compressed decision problems in hyperbolic groups. In Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS\u201919),LIPIcs, Vol. 126. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 37:1\u201337:16."},{"key":"e_1_3_2_36_2","series-title":"London Mathematical Society Student Texts","doi-asserted-by":"crossref","DOI":"10.1017\/9781316588246","volume-title":"Groups, Languages and Automata","author":"Holt Derek F.","year":"2017","unstructured":"Derek F. Holt, Sarah Rees, and Claas E. R\u00f6ver. 2017. Groups, Languages and Automata. London Mathematical Society Student Texts, Vol. 88. Cambridge University Press. DOI:10.1017\/9781316588246"},{"issue":"1","key":"e_1_3_2_37_2","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1006\/inco.1996.0071","article-title":"Logspace and logtime leaf languages","volume":"129","author":"Jenner Birgit","year":"1996","unstructured":"Birgit Jenner, Pierre McKenzie, and Denis Th\u00e9rien. 1996. Logspace and logtime leaf languages. Inf. Comput. 129, 1 (1996), 21\u201333.","journal-title":"Inf. Comput."},{"issue":"3","key":"e_1_3_2_38_2","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0890-5401(89)90008-4","article-title":"The iterated mod problem","volume":"80","author":"Karloff Howard J.","year":"1989","unstructured":"Howard J. Karloff and Walter L. Ruzzo. 1989. The iterated mod problem. Inf. Comput. 80, 3 (1989), 193\u2013204.","journal-title":"Inf. Comput."},{"issue":"5","key":"e_1_3_2_39_2","doi-asserted-by":"crossref","first-page":"1459","DOI":"10.1007\/s00453-017-0343-z","article-title":"Evaluation of circuits over nilpotent and polycyclic groups","volume":"80","author":"K\u00f6nig Daniel","year":"2018","unstructured":"Daniel K\u00f6nig and Markus Lohrey. 2018. Evaluation of circuits over nilpotent and polycyclic groups. Algorithmica 80, 5 (2018), 1459\u20131492.","journal-title":"Algorithmica"},{"issue":"6","key":"e_1_3_2_40_2","doi-asserted-by":"crossref","first-page":"979","DOI":"10.1142\/S0218196718500431","article-title":"Parallel identity testing for skew circuits with big powers and applications","volume":"28","author":"K\u00f6nig Daniel","year":"2018","unstructured":"Daniel K\u00f6nig and Markus Lohrey. 2018. Parallel identity testing for skew circuits with big powers and applications. Int. J. Arch. Comput. 28, 6 (2018), 979\u20131004.","journal-title":"Int. J. Arch. Comput."},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/bdl043"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.4171\/JEMS\/220"},{"key":"e_1_3_2_43_2","series-title":"Proceedings of the 31th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201906),","first-page":"681","volume":"4162","author":"Lifshits Yury","year":"2006","unstructured":"Yury Lifshits and Markus Lohrey. 2006. Querying and embedding compressed texts. In Proceedings of the 31th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201906),Lecture Notes in Computer Science, Vol. 4162. Springer, 681\u2013692."},{"issue":"3","key":"e_1_3_2_44_2","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1145\/322017.322031","article-title":"Word problems solvable in logspace","volume":"24","author":"Lipton Richard J.","year":"1977","unstructured":"Richard J. Lipton and Yechezkel Zalcstein. 1977. Word problems solvable in logspace. J. Assoc. Comput. Mach. 24, 3 (1977), 522\u2013526.","journal-title":"J. Assoc. Comput. Mach."},{"issue":"5","key":"e_1_3_2_45_2","doi-asserted-by":"crossref","first-page":"1210","DOI":"10.1137\/S0097539704445950","article-title":"Word problems and membership problems on compressed words","volume":"35","author":"Lohrey Markus","year":"2006","unstructured":"Markus Lohrey. 2006. Word problems and membership problems on compressed words. SIAM J. Comput. 35, 5 (2006), 1210\u20131240.","journal-title":"SIAM J. Comput."},{"issue":"6","key":"e_1_3_2_46_2","doi-asserted-by":"crossref","first-page":"951","DOI":"10.1016\/j.ic.2011.01.009","article-title":"Leaf languages and string compression","volume":"209","author":"Lohrey Markus","year":"2011","unstructured":"Markus Lohrey. 2011. Leaf languages and string compression. Inf. Comput. 209, 6 (2011), 951\u2013965.","journal-title":"Inf. Comput."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-0748-9"},{"key":"e_1_3_2_48_2","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/j.ic.2013.01.002","article-title":"Isomorphism of regular trees and words","volume":"224","author":"Lohrey Markus","year":"2013","unstructured":"Markus Lohrey and Christian Mathissen. 2013. Isomorphism of regular trees and words. Inf. Comput. 224 (2013), 71\u2013105.","journal-title":"Inf. Comput."},{"key":"e_1_3_2_49_2","series-title":"Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS\u201919),","first-page":"43:1\u201343:15","volume":"138","author":"Lohrey Markus","year":"2019","unstructured":"Markus Lohrey and Armin Wei\u00df. 2019. The power word problem. In Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS\u201919),LIPIcs, Vol. 138. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 43:1\u201343:15."},{"key":"e_1_3_2_50_2","first-page":"191","volume-title":"Proceedings of the 6th Annual Symposium on Switching Circuit Theory and Logical Design","author":"II Philip M. Lewis","year":"1965","unstructured":"Philip M. Lewis II, Richard Edwin Stearns, and Juris Hartmanis. 1965. Memory bounds for recognition of context-free and context-sensitive languages. In Proceedings of the 6th Annual Symposium on Switching Circuit Theory and Logical Design. IEEE Computer Society, 191\u2013202."},{"key":"e_1_3_2_51_2","first-page":"213","volume-title":"Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201994)","author":"Mehlhorn Kurt","year":"1994","unstructured":"Kurt Mehlhorn, R. Sundar, and Christian Uhrig. 1994. Maintaining dynamic sequences under equality-tests in polylogarithmic time. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201994). ACM\/SIAM, 213\u2013222. http:\/\/dl.acm.org\/citation.cfm?id=314464.314496."},{"key":"e_1_3_2_52_2","series-title":"Mathematical Surveys and Monographs","doi-asserted-by":"crossref","DOI":"10.1090\/surv\/117","volume-title":"Self-similar Groups","author":"Nekrashevych Volodymyr","year":"2005","unstructured":"Volodymyr Nekrashevych. 2005. Self-similar Groups. Mathematical Surveys and Monographs, Vol. 117. American Mathematical Society, Providence, RI. DOI:10.1090\/surv\/117"},{"key":"e_1_3_2_53_2","first-page":"1","article-title":"On the algorithmic unsolvability of the word problem in group theory","author":"Novikov Piotr S.","year":"1955","unstructured":"Piotr S. Novikov. 1955. On the algorithmic unsolvability of the word problem in group theory. Trudy Mat. Inst. Steklov (1955), 1\u2013143.","journal-title":"Trudy Mat. Inst. Steklov"},{"key":"e_1_3_2_54_2","series-title":"Proceedings of the Second Annual European Symposium on Algorithms (ESA\u201994),","first-page":"460","volume":"855","author":"Plandowski Wojciech","year":"1994","unstructured":"Wojciech Plandowski. 1994. Testing equivalence of morphisms on context-free languages. In Proceedings of the Second Annual European Symposium on Algorithms (ESA\u201994),Lecture Notes in Computer Science, Vol. 855. Springer, 460\u2013470. DOI:10.1007\/BFb0049431"},{"key":"e_1_3_2_55_2","volume-title":"Parallel Algorithms for Group Word Problems","author":"Robinson David","year":"1993","unstructured":"David Robinson. 1993. Parallel Algorithms for Group Word Problems. Ph. D. Dissertation. University of California, San Diego."},{"key":"e_1_3_2_56_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-4176-8","volume-title":"An Introduction to the Theory of Groups","author":"Rotman Joseph J.","year":"1995","unstructured":"Joseph J. Rotman. 1995. An Introduction to the Theory of Groups (4th ed.). Springer."},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"e_1_3_2_58_2","first-page":"417","volume-title":"Proceedings of the International Symposium on Fundamentals of Computation Theory (FCT\u201979)","author":"Simon Hans-Ulrich","year":"1979","unstructured":"Hans-Ulrich Simon. 1979. Word problems for groups and contextfree recognition. In Proceedings of the International Symposium on Fundamentals of Computation Theory (FCT\u201979). Akademie-Verlag, 417\u2013422."},{"key":"e_1_3_2_59_2","first-page":"77","volume-title":"Proceedings of the 19th Annual ACM Symposium on Theory of Computing","author":"Smolensky Roman","year":"1987","unstructured":"Roman Smolensky. 1987. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing. 77\u201382. DOI:10.1145\/28395.28404"},{"issue":"2","key":"e_1_3_2_60_2","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1016\/0021-8693(72)90058-0","article-title":"Free subgroups in linear groups","volume":"20","author":"Tits Jacques","year":"1972","unstructured":"Jacques Tits. 1972. Free subgroups in linear groups. J. Algebr. 20, 2 (1972), 250\u2013270.","journal-title":"J. Algebr."},{"key":"e_1_3_2_61_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity","author":"Vollmer Heribert","year":"1999","unstructured":"Heribert Vollmer. 1999. Introduction to Circuit Complexity. Springer, Berlin."},{"key":"e_1_3_2_62_2","first-page":"265","article-title":"The parallel complexity of some constructions in combinatorial group theory","volume":"26","author":"Waack Stephan","year":"1990","unstructured":"Stephan Waack. 1990. The parallel complexity of some constructions in combinatorial group theory. J. Inf. Process. Cybernet. EIK 26 (1990), 265\u2013281.","journal-title":"J. Inf. Process. Cybernet. EIK"},{"key":"e_1_3_2_63_2","first-page":"6:1\u20136:17","volume-title":"Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS\u201920)","author":"W\u00e4chter Jan Philipp","year":"2020","unstructured":"Jan Philipp W\u00e4chter and Armin Wei\u00df. 2020. An automaton group with PSPACE-complete word problem. In Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS\u201920). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 6:1\u20136:17. DOI:10.4230\/LIPIcs.STACS.2020.6"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01293535"},{"key":"e_1_3_2_65_2","doi-asserted-by":"crossref","first-page":"44","DOI":"10.3934\/era.2009.16.44","article-title":"Research announcement: The structure of groups with a quasiconvex hierarchy","volume":"16","author":"Wise Daniel T.","year":"2009","unstructured":"Daniel T. Wise. 2009. Research announcement: The structure of groups with a quasiconvex hierarchy. Electr. Res. Announce. Math. Sci. 16 (2009), 44\u201355.","journal-title":"Electr. Res. Announce. Math. Sci."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3569708","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3569708","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:57Z","timestamp":1750182537000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3569708"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,31]]},"references-count":64,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1145\/3569708"],"URL":"https:\/\/doi.org\/10.1145\/3569708","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,31]]},"assertion":[{"value":"2021-08-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-24","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-02-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}