Knapsack Problems for Wreath Products
From MaRDI portal
Publication:3304131
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
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
