{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:02Z","timestamp":1740109382753,"version":"3.37.3"},"reference-count":62,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,5,7]],"date-time":"2024-05-07T00:00:00Z","timestamp":1715040000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,5,7]],"date-time":"2024-05-07T00:00:00Z","timestamp":1715040000000},"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":["LO 748\/12-2DI 435\/7-1"],"award-info":[{"award-number":["LO 748\/12-2DI 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":[[2024,6]]},"abstract":"Abstract<\/jats:title>The power word problem for a group $$\\varvec{G}$$<\/jats:tex-math>\n \n G<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> asks whether an expression $$\\varvec{u_1^{x_1} \\cdots u_n^{x_n}}$$<\/jats:tex-math>\n \n \n u<\/mml:mi>\n 1<\/mml:mn>\n \n x<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n <\/mml:msubsup>\n \u22ef<\/mml:mo>\n \n u<\/mml:mi>\n n<\/mml:mi>\n \n x<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n <\/mml:msubsup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where the $$\\varvec{u_i}$$<\/jats:tex-math>\n \n \n u<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> are words over a finite set of generators of $$\\varvec{G}$$<\/jats:tex-math>\n \n G<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and the $$\\varvec{x_i}$$<\/jats:tex-math>\n \n \n x<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> binary encoded integers, is equal to the identity of $$\\varvec{G}$$<\/jats:tex-math>\n \n G<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. It is a restriction of the compressed word problem, where the input word is represented by a straight-line program (i.e., an algebraic circuit over $$\\varvec{G}$$<\/jats:tex-math>\n \n G<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>). We start by showing some easy results concerning the power word problem. In particular, the power word problem for a group $$\\varvec{G}$$<\/jats:tex-math>\n \n G<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is $$\\varvec{\\textsf{uNC}^{1}}$$<\/jats:tex-math>\n \n \n uNC<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-many-one reducible to the power word problem for a finite-index subgroup of $$\\varvec{G}$$<\/jats:tex-math>\n \n G<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. For our main result, we consider graph products of groups that do not have elements of order two. We show that the power word problem in a fixed such graph product is $$\\varvec{\\textsf{AC} ^0}$$<\/jats:tex-math>\n \n \n AC<\/mml:mi>\n 0<\/mml:mn>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-Turing-reducible to the word problem for the free group $$\\varvec{F_2}$$<\/jats:tex-math>\n \n \n F<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and the power word problems of the base groups. Furthermore, we look into the uniform power word problem in a graph product, where the dependence graph and the base groups are part of the input. Given a class of finitely generated groups $$\\varvec{\\mathcal {C}}$$<\/jats:tex-math>\n \n C<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> without order two elements, the uniform power word problem in a graph product can be solved in $$\\varvec{\\textsf{AC} ^0[\\textsf{C}_=\\textsf{L} ^{{{\\,\\textrm{UPowWP}\\,}}(\\mathcal {C})}]}$$<\/jats:tex-math>\n \n \n AC<\/mml:mi>\n 0<\/mml:mn>\n <\/mml:msup>\n \n [<\/mml:mo>\n \n C<\/mml:mi>\n =<\/mml:mo>\n <\/mml:msub>\n \n L<\/mml:mi>\n \n \n \n UPowWP<\/mml:mtext>\n \n <\/mml:mrow>\n (<\/mml:mo>\n C<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where $$\\varvec{{{\\,\\textrm{UPowWP}\\,}}(\\mathcal {C})}$$<\/jats:tex-math>\n \n \n \n UPowWP<\/mml:mtext>\n \n <\/mml:mrow>\n (<\/mml:mo>\n C<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> denotes the uniform power word problem for groups from the class $$\\varvec{\\mathcal {C}}$$<\/jats:tex-math>\n \n C<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. As a consequence of our results, the uniform knapsack problem in right-angled Artin groups is $$\\varvec{\\textsf{NP}}$$<\/jats:tex-math>\n \n NP<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-complete. The present paper is a combination of the two conference papers (Lohrey and Wei\u00df 2019b, Stober and Wei\u00df 2022a). In Stober and Wei\u00df (2022a) our results on graph products were wrongly stated without the additional assumption that the base groups do not have elements of order two. In the present work we correct this mistake. While we strongly conjecture that the result as stated in Stober and Wei\u00df (2022a) is true, our proof relies on this additional assumption.<\/jats:p>","DOI":"10.1007\/s00224-024-10173-z","type":"journal-article","created":{"date-parts":[[2024,5,7]],"date-time":"2024-05-07T08:01:57Z","timestamp":1715068917000},"page":"403-464","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Power Word Problem in Graph Products"],"prefix":"10.1007","volume":"68","author":[{"given":"Markus","family":"Lohrey","sequence":"first","affiliation":[]},{"given":"Florian","family":"Stober","sequence":"additional","affiliation":[]},{"given":"Armin","family":"Wei\u00df","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,5,7]]},"reference":[{"key":"10173_CR1","first-page":"33","volume":"13","author":"E Allender","year":"2004","unstructured":"Allender, E.: Arithmetic circuits and counting complexity classes. Complexity of Computations and Proofs, Quaderni di Matematica 13, 33\u201372 (2004)","journal-title":"Complexity of Computations and Proofs, Quaderni di Matematica"},{"issue":"1","key":"10173_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1051\/ita\/1996300100011","volume":"30","author":"E Allender","year":"1996","unstructured":"Allender, E., Ogihara, M.: Relationships among PL, #L, and the determinant. RAIRO Theor. Inf. Appl. 30(1), 1\u201321 (1996). https:\/\/doi.org\/10.1051\/ita\/1996300100011","journal-title":"RAIRO Theor. Inf. Appl."},{"key":"10173_CR3","doi-asserted-by":"publisher","unstructured":"Allender, E., Balaji, N., Datta, S.: Low-depth uniform threshold circuits and the bit-complexity of straight line programs. In: Mathematical Foundations of Computer Science 2014 \u2013 39th International Symposium. Proceedings, Part II. Lecture Notes in Computer Science, vol. 8635, pp. 13\u201324. Springer (2014). https:\/\/doi.org\/10.1007\/978-3-662-44465-8_2","DOI":"10.1007\/978-3-662-44465-8_2"},{"issue":"4","key":"10173_CR4","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/BF00993053","volume":"8","author":"AV Anisimov","year":"1979","unstructured":"Anisimov, A.V., Knuth, D.E.: Inhomogeneous sorting. Int. J. Parallel Program 8(4), 255\u2013260 (1979). https:\/\/doi.org\/10.1007\/BF00993053","journal-title":"Int. J. Parallel Program"},{"key":"10173_CR5","doi-asserted-by":"publisher","unstructured":"Arora, S., Barak, B.: Computational Complexity - A Modern Approach. Cambridge University Press (2009). https:\/\/doi.org\/10.1017\/CBO9780511804090","DOI":"10.1017\/CBO9780511804090"},{"key":"10173_CR6","doi-asserted-by":"publisher","unstructured":"Barrington, D.A.M.: Bounded-width polynomial-size branching programs recognize exactly those languages in $${NC}^1$$. In: Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, pp. 1\u20135 (1986). https:\/\/doi.org\/10.1145\/12130.12131","DOI":"10.1145\/12130.12131"},{"key":"10173_CR7","doi-asserted-by":"publisher","unstructured":"Bartholdi, L., Grigorchuk, R.I., \u0160uni\u1e31, Z.: Branch groups. In: Handbook of Algebra, Vol. 3. Handb. Algebr., vol. 3, pp. 989\u20131112. Elsevier\/North-Holland Amsterdam (2003). https:\/\/doi.org\/10.1016\/S1570-7954(03)80078-5","DOI":"10.1016\/S1570-7954(03)80078-5"},{"key":"10173_CR8","doi-asserted-by":"publisher","DOI":"10.1145\/3569708","author":"L Bartholdi","year":"2022","unstructured":"Bartholdi, L., Figelius, M., Lohrey, M., Wei\u00df, A.: Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems. ACM Trans. Comput. Theory (2022). https:\/\/doi.org\/10.1145\/3569708","journal-title":"ACM Trans. Comput. Theory"},{"issue":"1","key":"10173_CR9","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1137\/S0097539793249530","volume":"26","author":"M Beaudry","year":"1997","unstructured":"Beaudry, M., McKenzie, P., P\u00e9ladeau, P., Th\u00e9rien, D.: Finite monoids: From word to circuit evaluation. SIAM J. Comput. 26(1), 138\u2013152 (1997). https:\/\/doi.org\/10.1137\/S0097539793249530","journal-title":"SIAM J. Comput."},{"key":"10173_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9771-7","author":"R Book","year":"1993","unstructured":"Book, R., Otto, F.: String-Rewriting Systems. Springer-Verlag (1993). https:\/\/doi.org\/10.1007\/978-1-4613-9771-7","journal-title":"Springer-Verlag"},{"issue":"2","key":"10173_CR11","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. of Math. 70(2), 207\u2013265 (1959). https:\/\/doi.org\/10.2307\/1970103","journal-title":"Ann. of Math."},{"issue":"3","key":"10173_CR12","doi-asserted-by":"publisher","first-page":"442","DOI":"10.1112\/jtopol\/jtp018","volume":"2","author":"J Crisp","year":"2009","unstructured":"Crisp, J., Godelle, E., Wiest, B.: The conjugacy problem in subgroups of right-angled Artin groups. J. Topol. 2(3), 442\u2013460 (2009). https:\/\/doi.org\/10.1112\/jtopol\/jtp018","journal-title":"J. Topol."},{"key":"10173_CR13","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/BF01456932","volume":"71","author":"M Dehn","year":"1911","unstructured":"Dehn, M.: Ueber unendliche diskontinuierliche Gruppen. Math. Ann. 71, 116\u2013144 (1911). https:\/\/doi.org\/10.1007\/BF01456932","journal-title":"Math. Ann."},{"key":"10173_CR14","doi-asserted-by":"publisher","unstructured":"Diekert, V., Rozenberg, G. (eds.): The Book of Traces, World Scientific (1995). https:\/\/doi.org\/10.1142\/2563","DOI":"10.1142\/2563"},{"issue":"3","key":"10173_CR15","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1142\/S0218196708004548","volume":"18","author":"V Diekert","year":"2008","unstructured":"Diekert, V., Lohrey, M.: Word equations over graph products. Internat. J. Algebra Comput. 18(3), 493\u2013533 (2008). https:\/\/doi.org\/10.1142\/S0218196708004548","journal-title":"Internat. J. Algebra Comput."},{"key":"10173_CR16","doi-asserted-by":"publisher","unstructured":"Diekert, V., Myasnikov, A.G., Wei\u00df, A.: Conjugacy in Baumslag\u2019s Group, Generic Case Complexity, and Division in Power Circuits. In: Latin American Theoretical Informatics Symposium. Lecture Notes in Computer Science, vol. 8392, pp. 1\u201312. Springer (2014). https:\/\/doi.org\/10.1007\/978-3-642-54423-1_1","DOI":"10.1007\/978-3-642-54423-1_1"},{"issue":"1","key":"10173_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0020-0190(85)90121-8","volume":"20","author":"C Duboc","year":"1985","unstructured":"Duboc, C.: Some properties of commutation in free partially commutative monoids. Inf. Process. Lett. 20(1), 1\u20134 (1985). https:\/\/doi.org\/10.1016\/0020-0190(85)90121-8","journal-title":"Inf. Process. Lett."},{"key":"10173_CR18","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0304-3975(86)90028-9","volume":"46","author":"C Duboc","year":"1986","unstructured":"Duboc, C.: On some equations in free partially commutative monoids. Theoret. Comput. Sci. 46, 159\u2013174 (1986). https:\/\/doi.org\/10.1016\/0304-3975(86)90028-9","journal-title":"Theoret. Comput. Sci."},{"key":"10173_CR19","doi-asserted-by":"publisher","unstructured":"Figelius, M., Ganardi, M., Lohrey, M., Zetzsche, G.: The complexity of knapsack problems in wreath products. In: 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020. LIPIcs, vol. 168, pp. 126\u2013112618. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.126","DOI":"10.4230\/LIPIcs.ICALP.2020.126"},{"issue":"1","key":"10173_CR20","doi-asserted-by":"publisher","first-page":"109","DOI":"10.2307\/2034009","volume":"16","author":"NJ Fine","year":"1965","unstructured":"Fine, N.J., Wilf, H.S.: Uniqueness theorems for periodic functions. Proc. Am. Math. Soc. 16(1), 109\u2013114 (1965). https:\/\/doi.org\/10.2307\/2034009","journal-title":"Proc. Am. Math. Soc."},{"key":"10173_CR21","doi-asserted-by":"publisher","unstructured":"Galby, E., Ouaknine, J., Worrell, J.: On matrix powering in low dimensions. In: Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015. LIPIcs, vol. 30, pp. 329\u2013340. Schloss Dagstuhl \u2013 Leibniz-Zentrum fuer Informatik (2015). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2015.329","DOI":"10.4230\/LIPIcs.STACS.2015.329"},{"key":"10173_CR22","doi-asserted-by":"publisher","unstructured":"Ganardi, M., K\u00f6nig, D., Lohrey, M., Zetzsche, G.: Knapsack problems for wreath products. In: Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018. LIPIcs, vol. 96, pp. 32\u201313213. Schloss Dagstuhl \u2013 Leibniz-Zentrum fuer Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2018.32","DOI":"10.4230\/LIPIcs.STACS.2018.32"},{"issue":"1","key":"10173_CR23","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0304-3975(91)90074-C","volume":"88","author":"M Garzon","year":"1991","unstructured":"Garzon, M., Zalcstein, Y.: The complexity of Grigorchuk groups with application to cryptography. Theoret. Comput. Sci. 88(1), 83\u201398 (1991). https:\/\/doi.org\/10.1016\/0304-3975(91)90074-C","journal-title":"Theoret. Comput. Sci."},{"key":"10173_CR24","doi-asserted-by":"publisher","unstructured":"Ge, G.: Testing equalities of multiplicative representations in polynomial time (extended abstract). In: Proceedings of the 34th Annual Symposium on Foundations of Computer Science, FOCS 1993, pp. 422\u2013426 (1993). https:\/\/doi.org\/10.1109\/SFCS.1993.366845","DOI":"10.1109\/SFCS.1993.366845"},{"key":"10173_CR25","unstructured":"Green, E.R.: Graph products of groups. PhD thesis, University of Leeds (1990)"},{"key":"10173_CR26","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. Appl. 14, 41\u201343 (1980). https:\/\/doi.org\/10.1007\/BF01078416","journal-title":"Funct. Anal. Appl."},{"key":"10173_CR27","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1137\/050643295","volume":"37","author":"Y Gurevich","year":"2007","unstructured":"Gurevich, Y., Schupp, P.: Membership problem for the modular group. SIAM J. Comput. 37, 425\u2013459 (2007). https:\/\/doi.org\/10.1137\/050643295","journal-title":"SIAM J. Comput."},{"issue":"08","key":"10173_CR28","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1142\/S0218196712400073","volume":"22","author":"N Haubold","year":"2012","unstructured":"Haubold, N., Lohrey, M., Mathissen, C.: Compressed decision problems for graph products and applications to (outer) automorphism groups. Internat. J. Algebra Comput. 22(08), 218\u2013230 (2012). https:\/\/doi.org\/10.1142\/S0218196712400073","journal-title":"Internat. J. Algebra Comput."},{"key":"10173_CR29","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1016\/S0022-0000(02)00025-9","volume":"65","author":"W Hesse","year":"2002","unstructured":"Hesse, W., Allender, E., Barrington, D.A.M.: Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. Syst. Sci. 65, 695\u2013716 (2002). https:\/\/doi.org\/10.1016\/S0022-0000(02)00025-9","journal-title":"J. Comput. Syst. Sci."},{"key":"10173_CR30","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1142\/S0218196700000078","volume":"10","author":"D Holt","year":"2000","unstructured":"Holt, D.: Word-hyperbolic groups have real-time word problem. Int. J. Algebr. Comput. 10, 221\u2013227 (2000). https:\/\/doi.org\/10.1142\/S0218196700000078","journal-title":"Int. J. Algebr. Comput."},{"key":"10173_CR31","doi-asserted-by":"publisher","unstructured":"Holt, D., Lohrey, M., Schleimer, S.: Compressed Decision Problems in Hyperbolic Groups. In: 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), vol. 126, pp. 37\u201313716. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2019.37","DOI":"10.4230\/LIPIcs.STACS.2019.37"},{"key":"10173_CR32","doi-asserted-by":"publisher","unstructured":"Jantzen, M.: Confluent String Rewriting. EATCS Monographs on Theoretical Computer Science, vol. 14. Springer-Verlag (1988). https:\/\/doi.org\/10.1007\/978-3-642-61549-8","DOI":"10.1007\/978-3-642-61549-8"},{"key":"10173_CR33","doi-asserted-by":"publisher","unstructured":"Kausch, J.: The parallel complexity of certain algorithmic problems in group theory. PhD thesis, University of Stuttgart (2017). https:\/\/doi.org\/10.18419\/opus-9152","DOI":"10.18419\/opus-9152"},{"key":"10173_CR34","doi-asserted-by":"publisher","unstructured":"K\u00f6nig, D., Lohrey, M., Zetzsche, G.: Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups. In: Algebra and Computer Science. Contemporary Mathematics, vol. 677, pp. 138\u2013153. American Mathematical Society (2016). https:\/\/doi.org\/10.1090\/conm\/677","DOI":"10.1090\/conm\/677"},{"issue":"5","key":"10173_CR35","doi-asserted-by":"publisher","first-page":"1459","DOI":"10.1007\/s00453-017-0343-z","volume":"80","author":"D K\u00f6nig","year":"2018","unstructured":"K\u00f6nig, D., Lohrey, M.: Evaluation of circuits over nilpotent and polycyclic groups. Algorithmica 80(5), 1459\u20131492 (2018). https:\/\/doi.org\/10.1007\/s00453-017-0343-z","journal-title":"Algorithmica"},{"issue":"2","key":"10173_CR36","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1142\/S0218196706003001","volume":"16","author":"D Kuske","year":"2006","unstructured":"Kuske, D., Lohrey, M.: Logical aspects of Cayley-graphs: the monoid case. Internat. J. Algebra Comput. 16(2), 307\u2013340 (2006). https:\/\/doi.org\/10.1142\/S0218196706003001","journal-title":"Internat. J. Algebra Comput."},{"key":"10173_CR37","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1145\/322017.322031","volume":"24","author":"RJ Lipton","year":"1977","unstructured":"Lipton, R.J., Zalcstein, Y.: Word problems solvable in logspace. J. ACM 24, 522\u2013526 (1977). https:\/\/doi.org\/10.1145\/322017.322031","journal-title":"J. ACM"},{"issue":"4","key":"10173_CR38","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1142\/S0129054105003248","volume":"16","author":"M Lohrey","year":"2005","unstructured":"Lohrey, M.: Decidability and complexity in automatic monoids. Int. J. Found. Comput. Sci. 16(4), 707\u2013722 (2005). https:\/\/doi.org\/10.1142\/S0129054105003248","journal-title":"Int. J. Found. Comput. Sci."},{"key":"10173_CR39","doi-asserted-by":"publisher","unstructured":"Lohrey, M.: The Compressed Word Problem for Groups. Springer Briefs in Mathematics, Springer (2014). https:\/\/doi.org\/10.1007\/978-1-4939-0748-9","DOI":"10.1007\/978-1-4939-0748-9"},{"key":"10173_CR40","doi-asserted-by":"publisher","unstructured":"Lohrey, M., Schleimer, S.: Efficient computation in groups via compression. In: CSR 2007, Proceedings, Springer, pp. 249\u2013258 (2007). https:\/\/doi.org\/10.1007\/978-3-540-74510-5_26","DOI":"10.1007\/978-3-540-74510-5_26"},{"key":"10173_CR41","unstructured":"Lohrey, M., Steinberg, B.: The submonoid and rational subset membership problems for graph groups. In: LATA 2007. Proceedings of the 1st International Conference on Language and Automata Theory and Applications, vol. Report 35\/07. Research Group on Mathematical Linguistics, Universitat Rovira i Virgili, Tarragona, pp. 367\u2013378 (2007)"},{"key":"10173_CR42","unstructured":"Lohrey, M., Wei\u00df, A.: The power word problem. arXiv:abs\/1904.08343 (2019a)"},{"key":"10173_CR43","doi-asserted-by":"publisher","unstructured":"Lohrey, M., Wei\u00df, A.: The Power Word Problem. In: MFCS 2019, Proceedings. LIPIcs, vol. 138, pp. 431\u20134315 (2019b). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2019.43","DOI":"10.4230\/LIPIcs.MFCS.2019.43"},{"key":"10173_CR44","doi-asserted-by":"publisher","unstructured":"Lohrey, M., Zetzsche, G.: Knapsack in graph groups. Theory Comput. Syst. 62(1), 192\u2013246 (2018). https:\/\/doi.org\/10.1007\/s00224-017-9808-3","DOI":"10.1007\/s00224-017-9808-3"},{"key":"10173_CR45","doi-asserted-by":"publisher","unstructured":"Lohrey, M., Zetzsche, G.: Knapsack and the power word problem in solvable Baumslag-Solitar groups. In: 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, Proceedings. LIPIcs, vol. 170, pp. 67\u201316715. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2020.67","DOI":"10.4230\/LIPIcs.MFCS.2020.67"},{"key":"10173_CR46","doi-asserted-by":"publisher","unstructured":"Lothaire, M.: Combinatorics on Words. Encyclopedia of Mathematics and Its Applications, vol. 17. Addison-Wesley (1983). https:\/\/doi.org\/10.1017\/CBO9780511566097. Cambridge University Press, 1997","DOI":"10.1017\/CBO9780511566097"},{"issue":"2","key":"10173_CR47","doi-asserted-by":"publisher","first-page":"764","DOI":"10.2307\/1968892","volume":"40","author":"W Magnus","year":"1939","unstructured":"Magnus, W.: On a theorem of Marshall Hall. Ann. Math. 40(2), 764\u2013768 (1939). https:\/\/doi.org\/10.2307\/1968892","journal-title":"Ann. Math."},{"key":"10173_CR48","doi-asserted-by":"publisher","unstructured":"Mattes, C., Wei\u00df, A.: Improved parallel algorithms for generalized baumslag groups. In: LATIN 2022: Theoretical Informatics \u2013 15th Latin American Symposium, Proceedings. Lecture Notes in Computer Science, vol. 13568, pp. 658\u2013675. Springer (2022). https:\/\/doi.org\/10.1007\/978-3-031-20624-5_40","DOI":"10.1007\/978-3-031-20624-5_40"},{"issue":"1","key":"10173_CR49","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1515\/gcc-2017-0005","volume":"9","author":"A Miasnikov","year":"2017","unstructured":"Miasnikov, A., Vassileva, S.: Log-space conjugacy problem in the Grigorchuk group. Groups Complex. Cryptol. 9(1), 77 (2017). https:\/\/doi.org\/10.1515\/gcc-2017-0005","journal-title":"Groups Complex. Cryptol."},{"issue":"4","key":"10173_CR50","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1142\/S0218196721500363","volume":"31","author":"M Modi","year":"2021","unstructured":"Modi, M., Seedhom, M., Ushakov, A.: Linear time algorithm for the conjugacy problem in the first Grigorchuk group. Internat. J. Algebra Comput. 31(4), 789\u2013806 (2021). https:\/\/doi.org\/10.1142\/S0218196721500363","journal-title":"Internat. J. Algebra Comput."},{"issue":"292","key":"10173_CR51","doi-asserted-by":"publisher","first-page":"987","DOI":"10.1090\/S0025-5718-2014-02880-9","volume":"84","author":"A Myasnikov","year":"2015","unstructured":"Myasnikov, A., Nikolaev, A., Ushakov, A.: Knapsack problems in groups. Math. Comput. 84(292), 987\u20131016 (2015). https:\/\/doi.org\/10.1090\/S0025-5718-2014-02880-9","journal-title":"Math. Comput."},{"key":"10173_CR52","doi-asserted-by":"publisher","unstructured":"Myasnikov, A.G., Wei\u00df, A.: TC$$^0$$ circuits for algorithmic problems in nilpotent groups. In: 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, Proceedings. LIPIcs, vol. 83, pp. 23\u201312314. Schloss Dagstuhl \u2013 Leibniz-Zentrum fuer Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2017.23","DOI":"10.4230\/LIPIcs.MFCS.2017.23"},{"issue":"6","key":"10173_CR53","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1142\/S0218196712500476","volume":"22","author":"AG Myasnikov","year":"2012","unstructured":"Myasnikov, A.G., Ushakov, A., Dong-Wook, W.: Power circuits, exponential algebra, and time complexity. Internat. J. Algebra Comput. 22(6), 3\u201353 (2012). https:\/\/doi.org\/10.1142\/S0218196712500476","journal-title":"Internat. J. Algebra Comput."},{"key":"10173_CR54","doi-asserted-by":"publisher","unstructured":"Nekrashevych, V.: Self-similar Groups. Mathematical Surveys and Monographs, vol. 117, p. 231. American Mathematical Society, Providence, RI (2005). https:\/\/doi.org\/10.1090\/surv\/117","DOI":"10.1090\/surv\/117"},{"key":"10173_CR55","unstructured":"Novikov, P.S.: On the algorithmic unsolvability of the word problem in group theory. Trudy Mat. Inst. Steklov, 1\u2013143 (1955). In Russian"},{"key":"10173_CR56","unstructured":"Robinson, D.: Parallel algorithms for group word problems. PhD thesis, University of California, San Diego (1993)"},{"key":"10173_CR57","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8594-1","author":"DJS Robinson","year":"1996","unstructured":"Robinson, D.J.S.: A Course in the Theory of Groups. Springer (1996). https:\/\/doi.org\/10.1007\/978-1-4419-8594-1","journal-title":"Springer"},{"key":"10173_CR58","doi-asserted-by":"publisher","unstructured":"Stober, F., Wei\u00df, A.: The power word problem in graph products. In: Developments in Language Theory \u2013 26th International Conference, DLT 2022, Tampa, FL, USA, May 9-13, 2022, Proceedings. Lecture Notes in Computer Science, vol. 13257, pp. 286\u2013298. Springer (2022a). https:\/\/doi.org\/10.1007\/978-3-031-05578-2_23","DOI":"10.1007\/978-3-031-05578-2_23"},{"key":"10173_CR59","doi-asserted-by":"crossref","unstructured":"Stober, F., Wei\u00df, A.: The power word problem in graph products. arXiv:2201.06543v2 (2022b)","DOI":"10.1007\/978-3-031-05578-2_23"},{"key":"10173_CR60","doi-asserted-by":"publisher","unstructured":"Vollmer, H.: Introduction to Circuit Complexity, Springer. Berlin (1999). https:\/\/doi.org\/10.1007\/978-3-662-03927-4","DOI":"10.1007\/978-3-662-03927-4"},{"issue":"5\u20136","key":"10173_CR61","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BFb0029647","volume":"26","author":"S Waack","year":"1990","unstructured":"Waack, S.: The parallel complexity of some constructions in combinatorial group theory. J. Inf. Process. Cybern. 26(5\u20136), 265\u2013281 (1990). https:\/\/doi.org\/10.1007\/BFb0029647","journal-title":"J. Inf. Process. Cybern."},{"issue":"1","key":"10173_CR62","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/S0747-7171(88)80024-5","volume":"6","author":"C Wrathall","year":"1988","unstructured":"Wrathall, C.: The word problem for free partially commutative groups. J. Symb. Comput. 6(1), 99\u2013104 (1988). https:\/\/doi.org\/10.1016\/S0747-7171(88)80024-5","journal-title":"J. Symb. Comput."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10173-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10173-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10173-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T02:03:56Z","timestamp":1718935436000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10173-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,7]]},"references-count":62,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["10173"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10173-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2024,5,7]]},"assertion":[{"value":"14 March 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}