Knapsack in hyperbolic groups

DOI10.1016/j.jalgebra.2019.04.008zbMath1485.20085arXiv1807.06774OpenAlexW2938649380WikidataQ128060041 ScholiaQ128060041MaRDI QIDQ5919299

Markus Lohrey

Publication date: 27 December 2019

Published in: Journal of Algebra (Search for Journal in Brave)

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

zbMATH Keywords

hyperbolic groupsknapsack problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Hyperbolic groups and nonpositively curved groups (20F67)

Related Items (4)

Decidability problem for exponential equations in finitely presented groups ⋮ Knapsack and the power word problem in solvable Baumslag–Solitar groups ⋮ Post's Correspondence Problem for hyperbolic and virtually nilpotent groups ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Knapsack problem for nilpotent groups
• Knapsack problems in products of groups
• Sur les groupes hyperboliques d'après Mikhael Gromov. (On the hyperbolic groups à la M. Gromov)
• Growing context-sensitive languages and Church-Rosser languages
• Knapsack in graph groups
• Semigroups, Presburger formulas, and languages
• Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth
• The Complexity of Model Checking (Collapsible) Higher−Order Pushdown Systems
• Verbal subgroups of hyperbolic groups have infinite width
• Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
• Knapsack Problems for Wreath Products
• ALMOST EVERY GROUP IS HYPERBOLIC
• On the Tape Complexity of Deterministic Context-Free Languages
• Knapsack in graph groups, HNN-extensions and amalgamated products
• WORD-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM
• Reducibility among Combinatorial Problems
• The co-word problem for the Higman-Thompson group is context-free
• DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
• THE LINEARITY OF THE CONJUGACY PROBLEM IN WORD-HYPERBOLIC GROUPS
• Knapsack problems in groups

This page was built for publication: Knapsack in hyperbolic groups