14 citations · 74 across the 41 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
math.GR2016
The Complexity of Knapsack in Graph Groups
Markus Lohrey, Georg Zetzsche
Myasnikov et al. have introduced the knapsack problem for arbitrary finitely generated groups. In previous work, the authors proved that for each graph group, the knapsack problem…
cs.CC2016
Circuit Evaluation for Finite Semirings
Moses Ganardi, Danny Hucke, Daniel König +1
The computational complexity of the circuit evaluation problem for finite semirings is considered, where semirings are not assumed to have an additive or multiplicative identity. T…
cs.FL2016
Efficient Quantile Computation in Markov Chains via Counting Problems for Parikh Images
Christoph Haase, Stefan Kiefer, Markus Lohrey
A cost Markov chain is a Markov chain whose transitions are labelled with non-negative integer costs. A fundamental problem on this model, with applications in the verification of…