14 citations · 86 across the 43 of their papers we have counts for
Showing 2015Show all
3 papers · 1 filter
math.GR2015★ 14 cited
Knapsack in graph groups, HNN-extensions and amalgamated products
Markus Lohrey, Georg Zetzsche
It is shown that the knapsack problem, which was introduced by Myasnikov et al. for arbitrary finitely generated groups, can be solved in NP for graph groups. This result even hold…
math.GR2015★ 6 cited
Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
Daniel König, Markus Lohrey, Georg Zetzsche
It is shown that the knapsack problem (introduced by Myasnikov, Nikolaev, and Ushakov) is undecidable in a direct product of sufficiently many copies of the discrete Heisenberg gro…
cs.FL2015★ 9 cited
An approach to computing downward closures
Georg Zetzsche
The downward closure of a word language is the set of all (not necessarily contiguous) subwords of its members. It is well-known that the downward closure of any language is regula…