{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:10Z","timestamp":1740109390979,"version":"3.37.3"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,5,9]],"date-time":"2023-05-09T00:00:00Z","timestamp":1683590400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,5,9]],"date-time":"2023-05-09T00:00:00Z","timestamp":1683590400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100018222","name":"Universit\u00e4t Siegen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100018222","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,8]]},"abstract":"Abstract<\/jats:title>It is shown that the subgroup membership problem for a virtually free group can be decided in polynomial time when all group elements are represented by so-called power words, i.e., words of the form $$p_1^{z_1} p_2^{z_2} \\cdots p_k^{z_k}$$<\/jats:tex-math>\n \n \n p<\/mml:mi>\n 1<\/mml:mn>\n \n z<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n <\/mml:msubsup>\n \n p<\/mml:mi>\n 2<\/mml:mn>\n \n z<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n <\/mml:msubsup>\n \u22ef<\/mml:mo>\n \n p<\/mml:mi>\n k<\/mml:mi>\n \n z<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n <\/mml:msubsup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Here the $$p_i$$<\/jats:tex-math>\n \n p<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> are explicit words over the generating set of the group and all $$z_i$$<\/jats:tex-math>\n \n z<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> are binary encoded integers. As a corollary, it follows that the subgroup membership problem for the matrix group $$\\textsf{GL}(2,\\mathbb {Z})$$<\/jats:tex-math>\n \n GL<\/mml:mi>\n (<\/mml:mo>\n 2<\/mml:mn>\n ,<\/mml:mo>\n Z<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> can be decided in polynomial time when elements of $$\\textsf{GL}(2,\\mathbb {Z})$$<\/jats:tex-math>\n \n GL<\/mml:mi>\n (<\/mml:mo>\n 2<\/mml:mn>\n ,<\/mml:mo>\n Z<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> are represented by matrices with binary encoded integers. For the same input representation, it also shown that one can compute in polynomial time the index of a given finitely generated subgroup of $$\\textsf{GL}(2,\\mathbb {Z})$$<\/jats:tex-math>\n \n GL<\/mml:mi>\n (<\/mml:mo>\n 2<\/mml:mn>\n ,<\/mml:mo>\n Z<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00224-023-10122-2","type":"journal-article","created":{"date-parts":[[2023,5,10]],"date-time":"2023-05-10T07:26:50Z","timestamp":1683703610000},"page":"1082-1107","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Subgroup Membership in GL(2,Z)"],"prefix":"10.1007","volume":"68","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4680-7198","authenticated-orcid":false,"given":"Markus","family":"Lohrey","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,5,9]]},"reference":[{"issue":"1\u20132","key":"10122_CR1","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. Theo Comput Sci 32(1\u20132), 61\u201376 (1984). https:\/\/doi.org\/10.1016\/0304-3975(84)90024-0","journal-title":"Theo Comput Sci"},{"key":"10122_CR2","doi-asserted-by":"publisher","unstructured":"Avenhaus J, Wi\u00dfmann D (1989) Using rewriting techniques to solve the generalized word problem in polycyclic groups. In : Proceedings of the ACM-SIGSAM 1989 International Symposium on Symbolic and Algebraic Computation, ISSAC 1989, pp.\u00a0322\u2013337. ACM Press. https:\/\/doi.org\/10.1145\/74540.74579","DOI":"10.1145\/74540.74579"},{"key":"10122_CR3","doi-asserted-by":"publisher","unstructured":"Babai L, Luks EM, Seress V \u00c1 (1987) Permutation groups in NC. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing, STOC 1987, pp.\u00a0409\u2013420. ACM. https:\/\/doi.org\/10.1145\/28395.28439","DOI":"10.1145\/28395.28439"},{"key":"10122_CR4","doi-asserted-by":"publisher","unstructured":"Bassino F, Kapovich I, Lohrey M, Miasnikov A, Nicaud C, Nikolaev A, Rivin I, Shpilrain V, Ushakov A , Weil P (2020) Compression techniques in group theory. In: Complexity and Randomness in Group Theory. De Gruyter, chapter\u00a04. https:\/\/doi.org\/10.1515\/9783110667028","DOI":"10.1515\/9783110667028"},{"key":"10122_CR5","doi-asserted-by":"publisher","unstructured":"Bell PC, Hirvensalo M, Potapov I (2017) The identity problem for matrix semigroups in $$\\sf SL\\sf _2(Z)$$ is NP-complete. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. SIAM, pp.\u00a0187\u2013206. https:\/\/doi.org\/10.1137\/1.9781611974782.13","DOI":"10.1137\/1.9781611974782.13"},{"key":"10122_CR6","first-page":"1188","volume":"269","author":"M Benois","year":"1969","unstructured":"Benois, M.: Parties rationnelles du groupe libre. Comptes rendus hebdomadaires des s\u00e9ances de l\u2019Acad\u00e9mie des sciences, S\u00e9ries A 269, 1188\u20131190 (1969)","journal-title":"Comptes rendus hebdomadaires des s\u00e9ances de l\u2019Acad\u00e9mie des sciences, S\u00e9ries A"},{"issue":"6","key":"10122_CR7","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0020-0190(86)90087-6","volume":"23","author":"M Benois","year":"1986","unstructured":"Benois, M., Sakarovitch, J.: On the complexity of some extended word problems defined by cancellation rules. Inf Process Lett 23(6), 281\u2013287 (1986). https:\/\/doi.org\/10.1016\/0020-0190(86)90087-6","journal-title":"Inf Process Lett"},{"key":"10122_CR8","doi-asserted-by":"publisher","unstructured":"Cadilhac M, Chistikov D, Zetzsche G (2020) Rational subsets of Baumslag-Solitar groups. In: Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, vol\u00a0168 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp.\u00a0116:1\u2013116:16. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.116","DOI":"10.4230\/LIPIcs.ICALP.2020.116"},{"key":"10122_CR9","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/j.jalgebra.2013.04.033","volume":"391","author":"J Delgado","year":"2013","unstructured":"Delgado, J., Ventura, E.: Algorithmic problems for free-abelian times free groups. J Algebra 391, 256\u2013283 (2013). https:\/\/doi.org\/10.1016\/j.jalgebra.2013.04.033","journal-title":"J Algebra"},{"key":"10122_CR10","doi-asserted-by":"publisher","unstructured":"Diekert V, Elder M (2017) Solutions of twisted word equations, EDT0L languages, and context-free groups. Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, vol\u00a080 of LIPIcs. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, pp.\u00a096:1\u201396:14. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.96","DOI":"10.4230\/LIPIcs.ICALP.2017.96"},{"key":"10122_CR11","doi-asserted-by":"publisher","unstructured":"Diekert V, Potapov I, Semukhin P (2020) Decidability of membership problems for flat rational subsets of GL(2,Q) and singular matrices. In: Proceedings of the 45th international symposium on symbolic and algebraic computation, ISSAC 2020. ACM, pp.\u00a0122\u2013129. https:\/\/doi.org\/10.1145\/3373207.3404038","DOI":"10.1145\/3373207.3404038"},{"issue":"4","key":"10122_CR12","doi-asserted-by":"publisher","first-page":"1827","DOI":"10.2140\/agt.2016.16.1827","volume":"16","author":"S Friedl","year":"2016","unstructured":"Friedl, S., Wilton, H.: The membership problem for 3-manifold groups is solvable. Algebraic Geometric Topology 16(4), 1827\u20131850 (2016). https:\/\/doi.org\/10.2140\/agt.2016.16.1827","journal-title":"Algebraic Geometric Topology"},{"key":"10122_CR13","unstructured":"Grunschlag Z (1999) Algorithms in Geometric Group Theory. PhD thesis, University of California at Berkley"},{"issue":"2","key":"10122_CR14","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). https:\/\/doi.org\/10.1137\/050643295","journal-title":"SIAM J Comput"},{"issue":"4","key":"10122_CR15","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1007\/s00224-013-9443-6","volume":"55","author":"A Je\u017c","year":"2014","unstructured":"Je\u017c, A.: The complexity of compressed membership problems for finite automata. Theory of Computing Systems 55(4), 685\u2013718 (2014). https:\/\/doi.org\/10.1007\/s00224-013-9443-6","journal-title":"Theory of Computing Systems"},{"key":"10122_CR16","doi-asserted-by":"publisher","unstructured":"Kapovich, I., Myasnikov, A.: Stallings foldings and subgroups of free groups. J Algebra 248(2), 608\u2013668 (2002). https:\/\/doi.org\/10.1006\/jabr.2001.9033","DOI":"10.1006\/jabr.2001.9033"},{"issue":"1","key":"10122_CR17","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1142\/S021819670500213X","volume":"15","author":"I Kapovich","year":"2005","unstructured":"Kapovich, I., Weidmann, R., Myasnikov, A.: Foldings, graphs of groups and the membership problem. Int J Algebra Comput 15(1), 95\u2013128 (2005). https:\/\/doi.org\/10.1142\/S021819670500213X","journal-title":"Int J Algebra Comput"},{"key":"10122_CR18","doi-asserted-by":"publisher","first-page":"442","DOI":"10.1016\/j.jalgebra.2017.05.037","volume":"488","author":"O Kharlampovich","year":"2017","unstructured":"Kharlampovich, O., Miasnikov, A., Weil, P.: Stallings graphs for quasi-convex subgroups. J Algebra 488, 442\u2013483 (2017). https:\/\/doi.org\/10.1016\/j.jalgebra.2017.05.037","journal-title":"J Algebra"},{"key":"10122_CR19","doi-asserted-by":"publisher","unstructured":"Kharlampovich OG, Myasnikov AG, Remeslennikov VN, Serbin DE (2004) Subgroups of fully residually free groups: algorithmic problems. In: group theory, statistics, and cryptography, vol\u00a0360 of contemporary mathematics. AMS, Providence, RI, pp.\u00a063\u2013101. https:\/\/doi.org\/10.1090\/conm\/360","DOI":"10.1090\/conm\/360"},{"key":"10122_CR20","unstructured":"Khukhro EI, Mazurov VD (2020) Unsolved problems in group theory. The Kourovka notebook. CoRR, arXiv:1401.0300v19, Problem\u00a012.50"},{"key":"10122_CR21","doi-asserted-by":"publisher","unstructured":"Ko S-K, Niskanen R, Potapov I (2018) On the identity problem for the special linear group and the Heisenberg group. In: Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, volume 107 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp.\u00a0132:1\u2013132:15. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.132","DOI":"10.4230\/LIPIcs.ICALP.2018.132"},{"key":"10122_CR22","doi-asserted-by":"publisher","unstructured":"Lohrey M (2014) The Compressed Word Problem for Groups. SpringerBriefs in Mathematics. Springer. https:\/\/doi.org\/10.1007\/978-1-4939-0748-9","DOI":"10.1007\/978-1-4939-0748-9"},{"key":"10122_CR23","doi-asserted-by":"publisher","unstructured":"Lohrey M, Wei\u00df A (2019) The power word problem. In: Proceedings of the 44th international symposium on mathematical foundations of computer science, MFCS 2019, volume 138 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pages 43:1\u201343:15. https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2019.43","DOI":"10.4230\/LIPIcs.MFCS.2019.43"},{"key":"10122_CR24","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511566097","author":"M Lothaire","year":"1997","unstructured":"Lothaire, M.: Combinatorics on Words. Cambridge University Press (1997). https:\/\/doi.org\/10.1017\/CBO9780511566097","journal-title":"Cambridge University Press"},{"key":"10122_CR25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61896-3","author":"RC Lyndon","year":"1977","unstructured":"Lyndon, R.C., Schupp, P.E.: Combinatorial Group Theory. Springer (1977). https:\/\/doi.org\/10.1007\/978-3-642-61896-3","journal-title":"Springer"},{"key":"10122_CR26","doi-asserted-by":"publisher","unstructured":"Mal\u2019cev AI (1983) On homomorphisms onto finite groups. American Math Soc Trans, Series 2 119:67\u201379. Translation from Ivanov. Gos. Ped. Inst. Ucen. Zap. 18 (1958) 49\u201360. https:\/\/doi.org\/10.1090\/trans2\/119","DOI":"10.1090\/trans2\/119"},{"issue":"8","key":"10122_CR27","doi-asserted-by":"publisher","first-page":"1493","DOI":"10.1142\/S0218196707003846","volume":"17","author":"L Markus-Epstein","year":"2007","unstructured":"Markus-Epstein, L.: Stallings foldings and subgroups of amalgams of finite groups. Int J Algebra Comput 17(8), 1493\u20131535 (2007). https:\/\/doi.org\/10.1142\/S0218196707003846","journal-title":"Int J Algebra Comput"},{"key":"10122_CR28","unstructured":"Miha\u012dlova KA (1966) The occurrence problem for direct products of groups. Math. USSR Sbornik 70:241\u2013251, English translation"},{"issue":"5","key":"10122_CR29","doi-asserted-by":"publisher","first-page":"895","DOI":"10.1142\/S0218196722500382","volume":"32","author":"Myasnikov AlG","year":"2022","unstructured":"AlG, Myasnikov, Wei\u00df, A.: Parallel complexity for nilpotent groups. Int J Algebra Comput 32(5), 895\u2013928 (2022). https:\/\/doi.org\/10.1142\/S0218196722500382","journal-title":"Int J Algebra Comput"},{"key":"10122_CR30","doi-asserted-by":"publisher","unstructured":"Potapov I, Semukhin P (2017) Decidability of the membership problem for $$2 \\times 2$$ integer matrices. In: Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017. SIAM, pp.\u00a0170\u2013186. https:\/\/doi.org\/10.1137\/1.9781611974782.12","DOI":"10.1137\/1.9781611974782.12"},{"key":"10122_CR31","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1112\/blms\/14.1.45","volume":"4","author":"E Rips","year":"1982","unstructured":"Rips, E.: Subgroups of small cancellation groups. Bulletin London Math Soc 4, 45\u201347 (1982). https:\/\/doi.org\/10.1112\/blms\/14.1.45","journal-title":"Bulletin London Math Soc"},{"key":"10122_CR32","doi-asserted-by":"publisher","unstructured":"Robinson DJS (1996) A Course in the Theory of Groups, 2nd edn. Springer. https:\/\/doi.org\/10.1007\/978-1-4419-8594-1","DOI":"10.1007\/978-1-4419-8594-1"},{"key":"10122_CR33","doi-asserted-by":"publisher","unstructured":"Romanovski\u012d NS (1974) Some algorithmic problems for solvable groups. Algebra Logic 13:13\u201316, English translation. https:\/\/doi.org\/10.1007\/BF01462922","DOI":"10.1007\/BF01462922"},{"key":"10122_CR34","doi-asserted-by":"publisher","unstructured":"Romanovski\u012d NS (1980) The occurrence problem for extensions of Abelian groups by nilpotent groups. Siberian Math J 21:273\u2013276, English translation. https:\/\/doi.org\/10.1007\/BF00968275","DOI":"10.1007\/BF00968275"},{"key":"10122_CR35","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1023\/A:1022155823425","volume":"96","author":"PE Schupp","year":"2003","unstructured":"Schupp, P.E.: Coxeter groups, 2-completion, perimeter reduction and subgroup separability. Geomet Dedicata 96, 179\u2013198 (2003). https:\/\/doi.org\/10.1023\/A:1022155823425","journal-title":"Geomet Dedicata"},{"key":"10122_CR36","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61856-7","author":"J-P Serre","year":"1980","unstructured":"Serre, J.-P.: Trees. Springer (1980). https:\/\/doi.org\/10.1007\/978-3-642-61856-7","journal-title":"Springer"},{"issue":"1","key":"10122_CR37","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1515\/jgth-2015-0028","volume":"19","author":"PV Silva","year":"2016","unstructured":"Silva, P.V., Soler-Escriv\u00e0, X., Ventura, E.: Finite automata for Schreier graphs of virtually free groups. J Group Theory 19(1), 25\u201354 (2016). https:\/\/doi.org\/10.1515\/jgth-2015-0028","journal-title":"J Group Theory"},{"key":"10122_CR38","doi-asserted-by":"publisher","unstructured":"Sims CC (1971) Computation with permutation groups. In: Proceedings of the 2nd ACM symposium on symbolic and algebraic manipulation, SYMSAC 1971. Association for Computing Machinery, p\u00a023\u201328. https:\/\/doi.org\/10.1145\/800204.806264","DOI":"10.1145\/800204.806264"},{"issue":"3","key":"10122_CR39","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/BF02095993","volume":"71","author":"JR Stallings","year":"1983","unstructured":"Stallings, J.R.: Topology of finite graphs. Invent Math 71(3), 551\u2013565 (1983). https:\/\/doi.org\/10.1007\/BF02095993","journal-title":"Topology of finite graphs. Invent Math"},{"issue":"6","key":"10122_CR40","doi-asserted-by":"publisher","first-page":"1031","DOI":"10.1142\/S0218196706003396","volume":"16","author":"Nicholas W. M Touikan","year":"2006","unstructured":"Touikan, Nicholas W. M.: A fast algorithm for Stallings\u2019 folding process. Int J Algebra Comput 16(6), 1031\u20131045 (2006). https:\/\/doi.org\/10.1142\/S0218196706003396","journal-title":"Int J Algebra Comput"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10122-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-023-10122-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10122-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T21:18:01Z","timestamp":1724447881000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-023-10122-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,9]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["10122"],"URL":"https:\/\/doi.org\/10.1007\/s00224-023-10122-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2023,5,9]]},"assertion":[{"value":"14 March 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 May 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}