Membership problems in infinite groups

DOI10.1007/978-3-031-64309-5_5MaRDI QIDQ7030916zbMATH OpenFDO

Authors Markus Lohrey

Publication date 7 February 2025

Full work available at URL https://doi.org/10.1007/978-3-031-64309-5_5

zbMATH Keywords

computational group theorydecidabilitydecision problemidentity problemknapsack problemmembership testingnilpotent groupsrational setsubgroup problem

Mathematics Subject Classification ID

Computational methods for problems pertaining to group theory (20-08) Residual properties and generalizations; residually finite groups (20E26) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Solvable groups, supersolvable groups (20F16) Geometric group theory (20F65) Formal languages and automata (68Q45)

Review text

This survey gives a comprehensive overview of membership problems in infinite finitely generated groups, including subgroup, submonoid, rational subset, identity, knapsack and context-free membership problems. The exposition combines classical undecidability results with recent advances on complexity and decidability in specific classes of groups, such as hyperbolic, nilpotent, metabelian, graph and Baumslag-Solitar groups. Several positive results rely on structural properties (e.g., finite index, co-context-freeness), while negative results are often obtained via reductions from classical decision problems. The final section lists open problems related to the decidability frontier in group-based computation.\N\NFor the entire collection see [Zbl 1554.68013].

Cites work

• An automata theoretic approach to the generalized word problem in graphs of groups.
• Characterizations of the decidability of some problems for regular trace languages
• Computable algebra and group embeddings
• Decidability of membership problems for flat rational subsets of GL(2, Q) and singular matrices
• Decidability of the membership problem for \(2\times 2\) integer matrices
• Equations in nilpotent groups.
• FOLDINGS, GRAPHS OF GROUPS AND THE MEMBERSHIP PROBLEM
• GROUPS WITH CONTEXT-FREE CO-WORD PROBLEM
• Growing context-sensitive languages and Church-Rosser languages
• scientific article; zbMATH DE number 3876579 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3762288 (Why is no real title available?)
• scientific article; zbMATH DE number 3257446 (Why is no real title available?)
• scientific article; zbMATH DE number 3339488 (Why is no real title available?)
• scientific article; zbMATH DE number 3056890 (Why is no real title available?)
• Invariant Measures and Growth Conditions
• Knapsack and the power word problem in solvable Baumslag–Solitar groups
• Knapsack in graph groups
• Knapsack in hyperbolic groups
• Knapsack problems in groups
• Occurrence problem for free solvable groups
• On homomorphisms onto finite groups
• On Reachability Problems for Low-Dimensional Matrix Semigroups
• On the existential theories of Büchi arithmetic and linear p-adic fields
• On the integer solutions of quadratic equations
• On the rational subset problem for groups.
• On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups
• Parallel complexity for nilpotent groups
• Parallel complexity in group theory
• Presburger arithmetic with stars, rational subsets of graph groups, and nested zero tests
• Rational subsets and submonoids of wreath products.
• Solvability of the problem of occurrence in finitely generated soluble groups of matrices over the field of algebraic numbers
• Some decision problems on integer matrices
• Some two-generator one-relator non-Hopfian groups
• Subgroups of small Cancellation Groups
• Submonoids and rational subsets of groups with infinitely many ends.
• The Compressed Word Problem for Groups
• The identity problem in nilpotent groups of bounded class
• The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete
• The occurrence problem for extensions of Abelian groups by nilpotent groups
• The power word problem in graph products
• The rational subset membership problem for groups: a survey
• The submonoid and rational subset membership problems for graph groups.
• Tilings and submonoids of metabelian groups.
• Undecidability of the submonoid membership problem for free nilpotent group of class l\geqslant 2 of sufficiently large rank

Cited in

(5)

• Ordering groups and the identity problem
• Membership problems in braid groups and Artin groups
• Membership problems in nilpotent groups
• On the ET0L subgroup membership problem in bounded automata groups
• Submonoid membership in n-dimensional lamplighter groups and S-unit equations

This page was built for publication: Membership problems in infinite groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7030916)