{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T11:11:02Z","timestamp":1758280262596,"version":"3.40.3"},"publisher-location":"Cham","reference-count":67,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030800482"},{"type":"electronic","value":"9783030800499"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"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":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-80049-9_30","type":"book-chapter","created":{"date-parts":[[2021,7,1]],"date-time":"2021-07-01T18:06:14Z","timestamp":1625162774000},"page":"330-341","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Compression Techniques in Group Theory"],"prefix":"10.1007","author":[{"given":"Markus","family":"Lohrey","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,7,2]]},"reference":[{"key":"30_CR1","first-page":"231","volume":"6","author":"SI Adjan","year":"1957","unstructured":"Adjan, S.I.: The unsolvability of certain algorithmic problems in the theory of groups. Trudy Moskov. Mat. Obsc. 6, 231\u2013298 (1957). in Russian","journal-title":"Trudy Moskov. Mat. Obsc."},{"key":"30_CR2","doi-asserted-by":"crossref","unstructured":"Agol, I.: The virtual Haken conjecture. Documenta Mathematica 18, 1045\u20131087 (2013). With an appendix by Ian Agol, Daniel Groves, and Jason Manning","DOI":"10.4171\/dm\/421"},{"issue":"4","key":"30_CR3","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1145\/792538.792540","volume":"50","author":"M Agrawal","year":"2003","unstructured":"Agrawal, M., Biswas, S.: Primality and identity testing via Chinese remaindering. J. Assoc. Comput. Mach. 50(4), 429\u2013443 (2003)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"1","key":"30_CR4","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/BF02950718","volume":"4","author":"E Artin","year":"1925","unstructured":"Artin, E.: Theorie der Z\u00f6pfe. Abh. Math. Semin. Univ. Hambg. 4(1), 47\u201372 (1925)","journal-title":"Abh. Math. Semin. Univ. Hambg."},{"issue":"1\u20132","key":"30_CR5","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0304-3975(84)90024-0","volume":"32","author":"J Avenhaus","year":"1984","unstructured":"Avenhaus, J., Madlener, K.: The Nielsen reduction and P-complete problems in free groups. Theoret. Comput. Sci. 32(1\u20132), 61\u201376 (1984)","journal-title":"Theoret. Comput. Sci."},{"key":"30_CR6","doi-asserted-by":"crossref","unstructured":"Babai, L., Szemer\u00e9di, E.: On the complexity of matrix group problems I. In: Proceedings of the 25th Annual Symposium on Foundations of Computer Science, FOCS 1984, pp. 229\u2013240 (1984)","DOI":"10.1109\/SFCS.1984.715919"},{"key":"30_CR7","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"DAM Barrington","year":"1989","unstructured":"Barrington, D.A.M.: Bounded-width polynomial-size branching programs recognize exactly those languages in $$\\text{ NC}^1$$. J. Comput. Syst. Sci. 38, 150\u2013164 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"30_CR8","unstructured":"Bartholdi, L., Figelius, M., Lohrey, M., Wei\u00df, A.: Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems. In: Proceedings of the 35th Computational Complexity Conference, CCC 2020. LIPIcs, vol. 169, pp. 29:1\u201329:29. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"issue":"1","key":"30_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)","journal-title":"SIAM J. Comput."},{"issue":"5\u20136","key":"30_CR10","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1142\/S0218196704001980","volume":"14","author":"J-C Birget","year":"2004","unstructured":"Birget, J.-C.: The groups of Richard Thompson and complexity. Int. J. Algebra Comput. 14(5\u20136), 569\u2013626 (2004)","journal-title":"Int. J. Algebra Comput."},{"key":"30_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. Math. Second Ser. 70, 207\u2013265 (1959)","journal-title":"Ann. Math. Second Ser."},{"key":"30_CR12","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y.: Parallel computation over hyperbolic groups. In: Proceedings of the 24th Annual Symposium on Theory of Computing, STOC 1992, pp. 106\u2013115. ACM Press (1992)","DOI":"10.1145\/129712.129723"},{"key":"30_CR13","doi-asserted-by":"publisher","first-page":"376","DOI":"10.2307\/2270453","volume":"31","author":"FB Cannonito","year":"1966","unstructured":"Cannonito, F.B.: Hierarchies of computable groups and the word problem. J. Symb. Log. 31, 376\u2013392 (1966)","journal-title":"J. Symb. Log."},{"issue":"7","key":"30_CR14","doi-asserted-by":"publisher","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","volume":"51","author":"M Charikar","year":"2005","unstructured":"Charikar, M., et al.: The smallest grammar problem. IEEE Trans. Inf. Theory 51(7), 2554\u20132576 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"30_CR15","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). In German","journal-title":"Math. Ann."},{"key":"30_CR16","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/BF01456725","volume":"72","author":"M Dehn","year":"1912","unstructured":"Dehn, M.: Transformation der Kurven auf zweiseitigen Fl\u00e4chen. Math. Ann. 72, 413\u2013421 (1912). In German","journal-title":"Math. Ann."},{"key":"30_CR17","doi-asserted-by":"crossref","unstructured":"Diekert, V., Laun, J., Ushakov, A.: Efficient algorithms for highly compressed data: the word problem in Higman\u2019s group is in P. Int. J. Algebra Comput. 22(8) (2012)","DOI":"10.1142\/S0218196712400085"},{"issue":"4","key":"30_CR18","doi-asserted-by":"publisher","first-page":"961","DOI":"10.1007\/s00453-016-0117-z","volume":"76","author":"V Diekert","year":"2016","unstructured":"Diekert, V., Myasnikov, A., Wei\u00df, A.: Conjugacy in Baumslag\u2019s group, generic case complexity, and division in power circuits. Algorithmica 76(4), 961\u2013988 (2016)","journal-title":"Algorithmica"},{"issue":"7","key":"30_CR19","doi-asserted-by":"publisher","first-page":"1299","DOI":"10.1142\/S0218196718500583","volume":"28","author":"W Dison","year":"2018","unstructured":"Dison, W., Einstein, E., Riley, T.R.: Taming the hydra: the word problem and extreme integer compression. Int. J. Algebra Comput. 28(7), 1299\u20131381 (2018)","journal-title":"Int. J. Algebra Comput."},{"issue":"3","key":"30_CR20","doi-asserted-by":"publisher","first-page":"507","DOI":"10.4171\/CMH\/294","volume":"88","author":"W Dison","year":"2013","unstructured":"Dison, W., Riley, T.R.: Hydra groups. Commentarii Mathematici Helvetici 88(3), 507\u2013540 (2013)","journal-title":"Commentarii Mathematici Helvetici"},{"key":"30_CR21","doi-asserted-by":"publisher","DOI":"10.1201\/9781439865699","volume-title":"Word Processing in Groups","author":"DBA Epstein","year":"1992","unstructured":"Epstein, D.B.A., Cannon, J.W., Holt, D.F., Levy, S.V.F., Paterson, M.S., Thurston, W.P.: Word Processing in Groups. Jones and Bartlett, Boston (1992)"},{"key":"30_CR22","unstructured":"Figelius, M., Ganardi, M., Lohrey, M., Zetzsche, G.: The complexity of knapsack problems in wreath products. In: Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020. LIPIcs, vol. 168, pp. 126:1\u2013126:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"key":"30_CR23","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)"},{"key":"30_CR24","doi-asserted-by":"publisher","unstructured":"Gromov, M.: Hyperbolic groups. In: Gersten, S.M. (ed.) Essays in Group Theory. MSRI, vol. 8, pp. 75\u2013263. Springer, New York (1987). https:\/\/doi.org\/10.1007\/978-1-4613-9586-7_3","DOI":"10.1007\/978-1-4613-9586-7_3"},{"issue":"2","key":"30_CR25","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1137\/050643295","volume":"37","author":"Y Gurevich","year":"2007","unstructured":"Gurevich, Y., Schupp, P.E.: Membership problem for the modular group. SIAM J. Comput. 37(2), 425\u2013459 (2007)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"30_CR26","doi-asserted-by":"publisher","first-page":"1890","DOI":"10.1016\/j.aim.2010.01.011","volume":"224","author":"F Haglund","year":"2010","unstructured":"Haglund, F., Wise, D.T.: Coxeter groups are virtually special. Adv. Math. 224(5), 1890\u20131903 (2010)","journal-title":"Adv. Math."},{"issue":"2","key":"30_CR27","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/s00224-010-9295-2","volume":"49","author":"N Haubold","year":"2011","unstructured":"Haubold, N., Lohrey, M.: Compressed word problems in HNN-extensions and amalgamated products. Theory Comput. Syst. 49(2), 283\u2013305 (2011). https:\/\/doi.org\/10.1007\/s00224-010-9295-2","journal-title":"Theory Comput. Syst."},{"key":"30_CR28","doi-asserted-by":"crossref","unstructured":"Haubold, N., Lohrey, M., Mathissen, C.: Compressed decision problems for graph products of groups and applications to (outer) automorphism groups. Int. J. Algebra Comput. 22(8) (2013)","DOI":"10.1142\/S0218196712400073"},{"key":"30_CR29","unstructured":"Hertrampf, U., Lautemann, C., Schwentick, T., Vollmer, H., Wagner, K.W.: On the power of polynomial time bit-reductions. In: Proceedings of the 8th Annual Structure in Complexity Theory Conference, pp. 200\u2013207. IEEE Computer Society Press (1993)"},{"issue":"1&2","key":"30_CR30","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0304-3975(95)00064-X","volume":"158","author":"Y Hirshfeld","year":"1996","unstructured":"Hirshfeld, Y., Jerrum, M., Moller, F.: A polynomial algorithm for deciding bisimilarity of normed context-free processes. Theoret. Comput. Sci. 158(1 & 2), 143\u2013159 (1996)","journal-title":"Theoret. Comput. Sci."},{"key":"30_CR31","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. Algebra Comput. 10, 221\u2013228 (2000)","journal-title":"Int. J. Algebra Comput."},{"key":"30_CR32","unstructured":"Holt, D., Lohrey, M., Schleimer, S.: Compressed decision problems in hyperbolic groups. In: Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019. LIPIcs, vol. 126, pp. 37:1\u201337:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"key":"30_CR33","unstructured":"Holt, D., Rees, S.: The compressed word problem in relatively hyperbolic groups. Technical report (2020). arxiv:2005.13917"},{"issue":"1","key":"30_CR34","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1145\/322358.322373","volume":"30","author":"OH Ibarra","year":"1983","unstructured":"Ibarra, O.H., Moran, S.: Probabilistic algorithms for deciding equivalence of straight-line programs. J. Assoc. Comput. Mach. 30(1), 217\u2013228 (1983)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"1\u20132","key":"30_CR35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-004-0182-6","volume":"13","author":"V Kabanets","year":"2004","unstructured":"Kabanets, V., Impagliazzo, R.: Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complex. 13(1\u20132), 1\u201346 (2004)","journal-title":"Comput. Complex."},{"issue":"2","key":"30_CR36","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1016\/S0021-8693(03)00167-4","volume":"264","author":"I Kapovich","year":"2003","unstructured":"Kapovich, I., Myasnikov, A., Schupp, P., Shpilrain, V.: Generic-case complexity, decision problems in group theory, and random walks. J. Algebra 264(2), 665\u2013694 (2003)","journal-title":"J. Algebra"},{"issue":"5","key":"30_CR37","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)","journal-title":"Algorithmica"},{"issue":"6","key":"30_CR38","doi-asserted-by":"publisher","first-page":"979","DOI":"10.1142\/S0218196718500431","volume":"28","author":"D K\u00f6nig","year":"2018","unstructured":"K\u00f6nig, D., Lohrey, M.: Parallel identity testing for skew circuits with big powers and applications. Int. J. Algebra Comput. 28(6), 979\u20131004 (2018)","journal-title":"Int. J. Algebra Comput."},{"issue":"3","key":"30_CR39","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. Assoc. Comput. Mach. 24(3), 522\u2013526 (1977)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"4","key":"30_CR40","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)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"5","key":"30_CR41","doi-asserted-by":"publisher","first-page":"1210","DOI":"10.1137\/S0097539704445950","volume":"35","author":"M Lohrey","year":"2006","unstructured":"Lohrey, M.: Word problems and membership problems on compressed words. SIAM J. Comput. 35(5), 1210\u20131240 (2006)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"30_CR42","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1515\/gcc-2012-0016","volume":"4","author":"M Lohrey","year":"2012","unstructured":"Lohrey, M.: Algorithmics on SLP-compressed strings: a survey. Groups Complex. Cryptol. 4(2), 241\u2013299 (2012)","journal-title":"Groups Complex. Cryptol."},{"key":"30_CR43","series-title":"SpringerBriefs in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-0748-9","volume-title":"The Compressed Word Problem for Groups","author":"M Lohrey","year":"2014","unstructured":"Lohrey, M.: The Compressed Word Problem for Groups. SM, Springer, New York (2014). https:\/\/doi.org\/10.1007\/978-1-4939-0748-9"},{"key":"30_CR44","unstructured":"Lohrey, M.: Subgroup membership in GL(2, Z). In: Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021. LIPIcs, vol. 187, pp. 51:1\u201351:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"key":"30_CR45","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/978-3-540-74510-5_26","volume-title":"Computer Science \u2013 Theory and Applications","author":"M Lohrey","year":"2007","unstructured":"Lohrey, M., Schleimer, S.: Efficient computation in groups via compression. In: Diekert, V., Volkov, M.V., Voronkov, A. (eds.) CSR 2007. LNCS, vol. 4649, pp. 249\u2013258. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-74510-5_26"},{"key":"30_CR46","unstructured":"Lohrey, M., Wei\u00df, A.: The power word problem. In: Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019. LIPIcs, vol. 138, pp. 43:1\u201343:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"key":"30_CR47","unstructured":"Lohrey, M., Zetzsche, G.: Knapsack and the power word problem in solvable Baumslag-Solitar groups. In: Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020. LIPIcs, vol. 170, pp. 67:1\u201367:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"issue":"3","key":"30_CR48","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1142\/S021819671000542X","volume":"20","author":"J Macdonald","year":"2010","unstructured":"Macdonald, J.: Compressed words and automorphisms in fully residually free groups. Int. J. Algebra Comput. 20(3), 343\u2013355 (2010)","journal-title":"Int. J. Algebra Comput."},{"issue":"1","key":"30_CR49","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01455888","volume":"106","author":"W Magnus","year":"1932","unstructured":"Magnus, W.: Das Identit\u00e4tsproblem f\u00fcr Gruppen mit einer definierenden Relation. Math. Ann. 106(1), 295\u2013307 (1932)","journal-title":"Math. Ann."},{"key":"30_CR50","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. Second Ser. 40, 764\u2013768 (1939)","journal-title":"Ann. Math. Second Ser."},{"key":"30_CR51","unstructured":"Mattes, C., Wei\u00df, A.: Parallel algorithms for power circuits and the word problem of the Baumslag group. CoRR, abs\/2102.09921 (2021)"},{"key":"30_CR52","unstructured":"Mehlhorn, K., Sundar, R., Uhrig, C.: Maintaining dynamic sequences under equality-tests in polylogarithmic time. In: Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1994, pp. 213\u2013222. ACM\/SIAM (1994)"},{"issue":"4","key":"30_CR53","doi-asserted-by":"publisher","first-page":"809","DOI":"10.1007\/s00224-018-9849-2","volume":"63","author":"A Miasnikov","year":"2019","unstructured":"Miasnikov, A., Vassileva, S., Wei\u00df, A.: The conjugacy problem in free solvable groups and wreath products of Abelian groups is in $$\\text{ TC}^0$$. Theory Comput. Syst. 63(4), 809\u2013832 (2019)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"30_CR54","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1016\/j.jalgebra.2011.07.024","volume":"345","author":"A Myasnikov","year":"2011","unstructured":"Myasnikov, A., Ushakov, A., Won, D.W.: The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable. J. Algebra 345(1), 324\u2013342 (2011)","journal-title":"J. Algebra"},{"key":"30_CR55","doi-asserted-by":"crossref","unstructured":"Myasnikov, A.G., Ushakov, A., Won, D.W.: Power circuits, exponential algebra, and time complexity. Int. J. Algebra Comput. 22(6) (2012)","DOI":"10.1142\/S0218196712500476"},{"key":"30_CR56","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/trans2\/009\/01","volume":"9","author":"PS Novikov","year":"1958","unstructured":"Novikov, P.S.: On the algorithmic unsolvability of the word problem in group theory. Am. Math. Soc. Transl. II Ser. 9, 1\u2013122 (1958)","journal-title":"Am. Math. Soc. Transl. II Ser."},{"key":"30_CR57","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/BFb0049431","volume-title":"Algorithms \u2014 ESA \u201994","author":"W Plandowski","year":"1994","unstructured":"Plandowski, W.: Testing equivalence of morphisms on context-free languages. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 460\u2013470. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/BFb0049431"},{"key":"30_CR58","first-page":"341","volume":"95","author":"MO Rabin","year":"1960","unstructured":"Rabin, M.O.: Computable algebra, general theory and theory of computable fields. Trans. Am. Math. Soc. 95, 341\u2013360 (1960)","journal-title":"Trans. Am. Math. Soc."},{"key":"30_CR59","unstructured":"Robinson, D.: Parallel algorithms for group word problems. Ph.D. thesis, University of California, San Diego (1993)"},{"key":"30_CR60","series-title":"Progress in Computer Science and Applied Logic","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/978-3-319-05446-9_7","volume-title":"Perspectives in Computational Complexity","author":"N Saxena","year":"2014","unstructured":"Saxena, N.: Progress on polynomial identity testing-II. In: Agrawal, M., Arvind, V. (eds.) Perspectives in Computational Complexity. PCSAL, vol. 26, pp. 131\u2013146. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-05446-9_7"},{"issue":"4","key":"30_CR61","doi-asserted-by":"publisher","first-page":"741","DOI":"10.4171\/CMH\/142","volume":"83","author":"S Schleimer","year":"2008","unstructured":"Schleimer, S.: Polynomial-time word problems. Commentarii Mathematici Helvetici 83(4), 741\u2013765 (2008)","journal-title":"Commentarii Mathematici Helvetici"},{"key":"30_CR62","unstructured":"Simon, H.-U.: Word problems for groups and contextfree recognition. In: Proceedings of Fundamentals of Computation Theory, FCT 1979, pp. 417\u2013422. Akademie-Verlag (1979)"},{"key":"30_CR63","first-page":"265","volume":"26","author":"S Waack","year":"1990","unstructured":"Waack, S.: The parallel complexity of some constructions in combinatorial group theory. J. Inf. Process. Cybern. EIK 26, 265\u2013281 (1990)","journal-title":"J. Inf. Process. Cybern. EIK"},{"key":"30_CR64","unstructured":"W\u00e4chter, J.P., Wei\u00df, A.: An automaton group with PSPACE-complete word problem. In: Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020. LIPIcs, vol. 154, pp. 6:1\u20136:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"key":"30_CR65","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/BF01214771","volume":"170","author":"BAF Wehrfritz","year":"1980","unstructured":"Wehrfritz, B.A.F.: On finitely generated soluble linear groups. Mathematische Zeitschrift 170, 155\u2013167 (1980)","journal-title":"Mathematische Zeitschrift"},{"key":"30_CR66","doi-asserted-by":"crossref","unstructured":"Wei\u00df, A.: A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups. In: Algebra and Computer Science, volume 677 of Contemporary Mathematics. American Mathematical Society (2016)","DOI":"10.1090\/conm\/677\/13628"},{"key":"30_CR67","doi-asserted-by":"publisher","DOI":"10.2307\/j.ctv1574pr6","volume-title":"The Structure of Groups with a Quasiconvex Hierarchy","author":"DT Wise","year":"2021","unstructured":"Wise, D.T.: The Structure of Groups with a Quasiconvex Hierarchy. Princeton University Press, Princeton (2021)"}],"container-title":["Lecture Notes in Computer Science","Connecting with Computability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-80049-9_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,5]],"date-time":"2023-11-05T14:47:55Z","timestamp":1699195675000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-80049-9_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030800482","9783030800499"],"references-count":67,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-80049-9_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"2 July 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CiE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Computability in Europe","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 July 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 July 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cie2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.cie2021.ugent.be\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"50","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"28","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"56% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}