Membership Problems in Infinite Groups

1. Aalbersberg, I.J., Hoogeboom, H.J.: Characterizations of the decidability of some problems for regular trace languages. Math. Syst. Theory 22, 1–19 (1989)

   Article  MathSciNet  Google Scholar 

2. Avenhaus, J., Wißmann, D.: Using rewriting techniques to solve the generalized word problem in polycyclic groups. In: Proceedings of the ISSAC 1989, pp. 322–337. ACM (1989)

   Google Scholar 

3. Baumslag, G., Cannonito, F.B., Miller, C.F., III.: Computable algebra and group embeddings. J. Algebra 69, 186–212 (1981)

   Article  MathSciNet  Google Scholar 

4. Baumslag, G., Solitar, D.: Some two-generator one-relator non-Hopfian groups. Bull. Am. Math. Soc. 68(3), 199–201 (1962)

   Article  MathSciNet  Google Scholar 

5. Bell, P.C., Hirvensalo, M., Potapov, I.: The membership problem for subsemigroups of GL2(Z) is NP-complete. Inf. Comput. 296, 105132 (2024)

   Article  Google Scholar 

6. Bell, P.C., Potapov, I.: On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups. Int. J. Found. Comput. Sci. 21(6), 963–978 (2010)

   Article  MathSciNet  Google Scholar 

7. Benois, M.: Parties rationnelles du groupe libre. Comptes rendus de l’Académie des sciences, Sér. A 269, 1188–1190 (1969)

   Google Scholar 

8. Bergsträßer, P., Ganardi, M., Zetzsche, G.: A characterization of wreath products where Knapsack is decidable. In: Proceedings of the STACS 2021. LIPIcs, vol. 187, pp. 11:1–11:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

   Google Scholar 

9. Berstel, J.: Transductions and context–free languages. Teubner (1979)

   Google Scholar 

10. Bodart, C.: Membership problems in nilpotent groups (2024). http://arxiv.org/abs/2401.15504

11. Bodart, C., Dong, R.: The identity problem in virtually solvable matrix groups over algebraic numbers (2024). http://arxiv.org/abs/2404.02264

12. Buntrock, G., Otto, F.: Growing context-sensitive languages and Church-Rosser languages. Inf. Comput. 141, 1–36 (1998)

    Article  MathSciNet  Google Scholar 

13. Cadilhac, M., Chistikov, D., Zetzsche, G.: Rational subsets of Baumslag-Solitar groups. In: Proceedings of the ICALP 2020. LIPIcs, vol. 168, pp. 116:1–116:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

    Google Scholar 

14. Choffrut, C., Karhumäki, J.: Some decision problems on integer matrices. RAIRO Theor. Inform. Appl. 39(1), 125–131 (2005)

    Article  MathSciNet  Google Scholar 

15. Colcombet, T., Ouaknine, J., Semukhin, P., Worrell, J.: On reachability problems for low-dimensional matrix semigroups. In: Proceedings of the ICALP 2019. LIPIcs, vol. 132, pp. 44:1–44:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

    Google Scholar 

16. Diekert, V., Potapov, I., Semukhin, P.: Decidability of membership problems for flat rational subsets of GL(2, Q) and singular matrices. In: Proceedings of the ISSAC 2020, pp. 122–129. ACM (2020)

    Google Scholar 

17. Dong, R.: Recent advances in algorithmic problems for semigroups. ACM SIGLOG News 10(4), 3–23 (2023)

    Article  Google Scholar 

18. Dong, R.: Semigroup algorithmic problems in metabelian groups (2023). http://arxiv.org/abs/2304.12893

19. Dong, R.: The identity problem in nilpotent groups of bounded class. In: Proceedings of the SODA 2024, pp. 3919–3959. SIAM (2024)

    Google Scholar 

20. Duchin, M., Liang, H., Shapiro, M.: Equations in nilpotent groups. Proc. Am. Math. Soc. 143, 4723–4731 (2015)

    Article  MathSciNet  Google Scholar 

21. Figelius, M., Ganardi, M., Lohrey, M., Zetzsche, G.: The complexity of knapsack problems in wreath products. In: Proceedings of the ICALP 2020. LIPIcs, vol. 168, pp.126:1–126:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

    Google Scholar 

22. Ganardi, M., Lohrey, M., Zetzsche, G.: Knapsack and the power word problem in solvable Baumslag-Solitar groups. Int. J. Algebra Comput. 33(3), 617–639 (2023)

    Article  MathSciNet  Google Scholar 

23. Gilman, R.H.: Computations with rational subsets of confluent groups. In: Fitch, J. (ed.) EUROSAM 1984. LNCS, vol. 174, pp. 207–212. Springer, Heidelberg (1984). https://doi.org/10.1007/BFb0032843

    Chapter  Google Scholar 

24. Grunewald, F., Segal, D.: On the integer solutions of quadratic equations. J. Reine Angew. Math. 569, 13–45 (2004)

    MathSciNet  Google Scholar 

25. Grunschlag, Z.: Algorithms in geometric group theory. Ph.D. thesis, University of California at Berkley (1999)

    Google Scholar 

26. Guépin, F., Haase, C., Worrell, J.: On the existential theories of Büchi arithmetic and linear p-adic fields. In: Proceedigns of the LICS 2019, pp. 1–10. IEEE (2019)

    Google Scholar 

27. Haase, C., Zetzsche, G.: Presburger arithmetic with stars, rational subsets of graph groups, and nested zero tests. In: Proceedings of the LICS 2019, pp. 1–14. IEEE (2019)

    Google Scholar 

28. Holt, D.F., Rees, S., Röver, C.E., Thomas, R.M.: Groups with context-free co-word problem. J. Lond. Math. Soc. 71(3), 643–657 (2005)

    Article  MathSciNet  Google Scholar 

29. Kambites, M., Silva, P.V., Steinberg, B.: On the rational subset problem for groups. J. Algebra 309(2), 622–639 (2007)

    Article  MathSciNet  Google Scholar 

30. Kapovich, I., Weidmann, R., Myasnikov, A.: Foldings, graphs of groups and the membership problem. Int. J. Algebra Comput. 15(1), 95–128 (2005)

    Article  MathSciNet  Google Scholar 

31. Kharlampovich, O.: A finitely presented solvable group with unsolvable word problem. Izvestiya Ak. Nauk, Ser. Math. 45(4), 852–873 (1981)

    Google Scholar 

32. König, 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–153. AMS (2016)

    Google Scholar 

33. Kopytov, V.M.: Solvability of the problem of occurrence in finitely generated soluble groups of matrices over the field of algebraic numbers. Algebra Logic 7(6), 388–393 (1968)

    Article  MathSciNet  Google Scholar 

34. Lohrey, M.: The Compressed Word Problem for Groups. Springer, Cham (2014)

    Book  Google Scholar 

35. Lohrey, M.: The rational subset membership problem for groups: a survey. In: Proceedings of the Groups St Andrews 2013. London Mathematical Society Lecture Note Series, vol. 422, pp. 368–389 (2016)

    Google Scholar 

36. Lohrey, M.: Knapsack in hyperbolic groups. J. Algebra 545, 390–415 (2020)

    Article  MathSciNet  Google Scholar 

37. Lohrey, M.: Subgroup membership in GL(2,Z). Theory Comput. Syst. (2023)

    Google Scholar 

38. Lohrey, M.: Parallel complexity in group theory. In: Languages and Automata: GAGTA BOOK 3. De Gruyter, to appear

    Google Scholar 

39. Lohrey, M., Steinberg, B.: The submonoid and rational subset membership problems for graph groups. J. Algebra 320(2), 728–755 (2008)

    Article  MathSciNet  Google Scholar 

40. Lohrey, M., Steinberg, B.: An automata theoretic approach to the generalized word problem in graphs of groups. Proc. Am. Math. Soc. 138, 445–453 (2010)

    Article  MathSciNet  Google Scholar 

41. Lohrey, M., Steinberg, B.: Submonoids and rational subsets of groups with infinitely many ends. J. Algebra 324(4), 970–983 (2010)

    Article  MathSciNet  Google Scholar 

42. Lohrey, M., Steinberg, B.: Tilings and submonoids of metabelian groups. Theory Comput. Syst. 48(2), 411–427 (2011)

    Article  MathSciNet  Google Scholar 

43. Lohrey, M., Steinberg, B., Zetzsche, G.: Rational subsets and submonoids of wreath products. Inf. Comput. 243, 191–204 (2015)

    Article  MathSciNet  Google Scholar 

44. Lohrey, M., Stober, F., Weiß, A.: The power word problem in graph products. Theory Comput. Syst. (2024). https://doi.org/10.1007/s00224-024-10173-z

45. Lohrey, M., Zetzsche, G.: Knapsack in graph groups. Theory Comput. Syst. 62(1), 192–246 (2018)

    Article  MathSciNet  Google Scholar 

46. Mal’cev, A.I.: On homomorphisms onto finite groups. Am. Math. Soc. Translations Series 2(119), 67–79 (1983)

    Article  Google Scholar 

47. Markov, A.: On certain insoluble problems concerning matrices. Dokl. Akad. Nauk SSSR 57, 539–542 (1947)

    MathSciNet  Google Scholar 

48. Mihaĭlova, K.A.: The occurrence problem for direct products of groups. Math. USSR Sbornik 70, 241–251 (1966). English translation

    Google Scholar 

49. Myasnikov, A., Nikolaev, A., Ushakov, A.: Knapsack problems in groups. Math. Comput. 84, 987–1016 (2015)

    Article  MathSciNet  Google Scholar 

50. Myasnikov, A., Weiß, A.: Parallel complexity for nilpotent groups. Int. J. Algebra Comput. 32(5), 895–928 (2022)

    Article  MathSciNet  Google Scholar 

51. Potapov, I., Semukhin, P.: Decidability of the membership problem for 2 \({\times }\) 2 integer matrices. In: Proceedings of the SODA 2017, pp. 170–186. SIAM (2017)

    Google Scholar 

52. Potthast, F.: Submonoid membership for wreath products. Bachelor thesis, University of Siegen (2020)

    Google Scholar 

53. Rips, E.: Subgroups of small cancellation groups. Bull. Lond. Math. Soc. 14, 45–47 (1982)

    Article  MathSciNet  Google Scholar 

54. Roman’kov, V.A.: Undecidability of the submonoid membership problem for free nilpotent group of class \(l \ge 2\) of sufficiently large rank. Izvestiya Math. 87(4), 798–816 (2023)

    Article  MathSciNet  Google Scholar 

55. Romanovskiĭ, N.S.: The occurrence problem for extensions of abelian groups by nilpotent groups. Sibirsk. Mat. Zh. 21, 170–174 (1980)

    MathSciNet  Google Scholar 

56. Rosenblatt, J.M.: Invariant measures and growth conditions. Trans. Am. Math. Soc. 193, 33–53 (1974)

    Article  MathSciNet  Google Scholar 

57. Shafrir, D.: A saturation theorem for submonoids of nilpotent groups and the identity problem (2024). http://arxiv.org/abs/2402.07337

58. Shafrir, D.: Bounded generation of submonoids of Heisenberg groups (2024). https://arxiv.org/pdf/2405.05939

59. Umirbaev, U.U.: The occurrence problem for free solvable groups. Sibirskiĭ Fond Algebry i Logiki. Algebra i Logika 34(2), 211–232, 243 (1995)

    Google Scholar 

Download references