Knapsack in graph groups
From MaRDI portal
Publication:1702854
DOI10.1007/s00224-017-9808-3zbMath1386.68073OpenAlexW2755307960MaRDI QIDQ1702854
Publication date: 1 March 2018
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-017-9808-3
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) 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 (10)
The power word problem in graph products ⋮ Decidability problem for exponential equations in finitely presented groups ⋮ Knapsack and the power word problem in solvable Baumslag–Solitar groups ⋮ The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete ⋮ Closure properties of knapsack semilinear groups ⋮ Bounded Context Switching for Valence Systems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Knapsack in hyperbolic groups
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The virtual Haken conjecture (with an appendix by Ian Agol, Daniel Groves and Jason Manning).
- Knapsack problems for NL
- Conjugacy in Baumslag's group, generic case complexity, and division in power circuits
- Knapsack problems in products of groups
- The submonoid and rational subset membership problems for graph groups.
- Coxeter groups are virtually special
- Unary finite automata vs. arithmetic progressions
- Research announcement: The structure of groups with a quasiconvex hierarchy.
- Combinatorics on traces
- Morse theory and finiteness properties of groups
- On linear and residual properties of graph products
- Membership problems for regular and context-free trace languages
- Isoperimetric functions of groups and computational complexity of the word problem
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Embeddings of graph braid and surface groups in right-angled Artin groups and braid groups.
- Subset sum problem in polycyclic groups
- The geometry and topology of reconfiguration
- Algorithmics on SLP-compressed strings: A survey
- Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth
- Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
- Combinatorics of Coxeter Groups
- Evaluating Matrix Circuits
- SOLVABILITY OF EQUATIONS IN GRAPH GROUPS IS DECIDABLE
- Efficient Computation in Groups Via Compression
- WORD EQUATIONS OVER GRAPH PRODUCTS
- The Smallest Grammar Problem
- Formal Languages and Groups as Memory
- On the complexity of integer programming
- Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
- On the Tape Complexity of Deterministic Context-Free Languages
- A Bound on Solutions of Linear Integer Equalities and Inequalities
- The Hardest Context-Free Language
- Knapsack in graph groups, HNN-extensions and amalgamated products
- The Complexity of Knapsack in Graph Groups
- Characterizations of the decidability of some problems for regular trace languages
- Reducibility among Combinatorial Problems
- Minimal solutions of linear diophantine systems : bounds and algorithms
- Computational Complexity
- The Compressed Word Problem for Groups
- LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE
- Knapsack problems in groups
- A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
- A Note on "The Comparability Graph of a Tree"
- Logspace computations in graph products
This page was built for publication: Knapsack in graph groups
