Knapsack Problems for Wreath Products

DOI10.4230/LIPIcs.STACS.2018.32zbMath1491.20078arXiv1709.09598WikidataQ122781748 ScholiaQ122781748MaRDI QIDQ3304131

Moses Ganardi, Markus Lohrey, Georg Zetzsche, Daniel König

Publication date: 5 August 2020

Full work available at URL: https://arxiv.org/abs/1709.09598

zbMATH Keywords

wreath productsknapsackdecision problems in group theory

Mathematics Subject Classification ID

Extensions, wreath products, and other compositions of groups (20E22) Decidability of theories and sets of sentences (03B25) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Lamplighter groups and automata, Decidability problem for exponential equations in finitely presented groups, Knapsack and the power word problem in solvable Baumslag–Solitar groups, Closure properties of knapsack semilinear groups, Unnamed Item, Unnamed Item, Unnamed Item, Knapsack in hyperbolic groups

Cites Work

• Unnamed Item
• Knapsack problem for nilpotent groups
• Subgroup distortion in wreath products of cyclic groups.
• Knapsack problems in products of groups
• Rational subsets and submonoids of wreath products.
• The conjugacy problem in free solvable groups and wreath products of abelian groups is in \({\mathsf {TC}^0}\)
• Subset sum problem in polycyclic groups
• Semigroups, Presburger formulas, and languages
• On a theorem of Marshall Hall
• Knapsack in graph groups, HNN-extensions and amalgamated products
• The Complexity of Knapsack in Graph Groups
• Reducibility among Combinatorial Problems
• The co-word problem for the Higman-Thompson group is context-free
• Knapsack problems in groups