Knapsack in graph groups
type: Item
instance of: scholarly article
title: Knapsack in graph groups
zbMATH Open document ID: 1386.68073
author: Markus Lohrey
author: Georg Zetzsche
published in: Theory of Computing Systems
publication date: 2018-03-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 20F10
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 6845595
zbMATH Keywords: graph groups
zbMATH Keywords: knapsack problems
zbMATH Keywords: combinatorial group theory
zbMATH Keywords: decision problems in group theory
MaRDI profile type: Publication
full work available at URL: s00224-017-9808-3
OpenAlex ID: W2755307960
cites work: Characterizations of the decidability of some problems for regular trace languages
cites work: The virtual Haken conjecture (with an appendix by Ian Agol, Daniel Groves and Jason Manning).
cites work: Computational Complexity
cites work: Q4875224
cites work: Membership problems for regular and context-free trace languages
cites work: Morse theory and finiteness properties of groups
cites work: Isoperimetric functions of groups and computational complexity of the word problem
cites work: Combinatorics of Coxeter Groups
cites work: The Smallest Grammar Problem
cites work: Embeddings of graph braid and surface groups in right-angled Artin groups and braid groups.
cites work: Combinatorics on traces
cites work: Logspace computations in graph products
cites work: WORD EQUATIONS OVER GRAPH PRODUCTS
cites work: SOLVABILITY OF EQUATIONS IN GRAPH GROUPS IS DECIDABLE
cites work: Conjugacy in Baumslag's group, generic case complexity, and division in power circuits
cites work: On linear and residual properties of graph products
cites work: Algorithmic meta theorems for circuit classes of constant and logarithmic depth
cites work: Knapsack problems in products of groups
cites work: A Bound on Solutions of Linear Integer Equalities and Inequalities
cites work: The geometry and topology of reconfiguration
cites work: The Hardest Context-Free Language
cites work: A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
cites work: Coxeter groups are virtually special
cites work: Uniform constant-depth threshold circuits for division and iterated multiplication.
cites work: Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
cites work: Q4526985
cites work: Knapsack problems for NL
cites work: Formal Languages and Groups as Memory
cites work: Reducibility among Combinatorial Problems
cites work: Evaluating Matrix Circuits
cites work: Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
cites work: LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE
cites work: Algorithmics on SLP-compressed strings: a survey
cites work: The Compressed Word Problem for Groups
cites work: Efficient Computation in Groups Via Compression
cites work: The submonoid and rational subset membership problems for graph groups.
cites work: Knapsack in graph groups, HNN-extensions and amalgamated products
cites work: The Complexity of Knapsack in Graph Groups
cites work: Q4145882
cites work: Q5545557
cites work: Q4941891
cites work: Knapsack problems in groups
cites work: Subset sum problem in polycyclic groups
cites work: On the complexity of integer programming
cites work: Minimal solutions of linear diophantine systems : bounds and algorithms
cites work: On the Tape Complexity of Deterministic Context-Free Languages
cites work: Unary finite automata vs. arithmetic progressions
cites work: Q4393484
cites work: Research announcement: The structure of groups with a quasiconvex hierarchy.
cites work: A Note on "The Comparability Graph of a Tree"
DOI: 10.1007/S00224-017-9808-3
description: scientific article; zbMATH DE number 6845595