5 papers
Streaming algorithms for groups and semigroups
Markus Lohrey, Lukas Lück, Alexander Thumm +1
We investigate deterministic and randomized streaming algorithms for word problems in finitely generated groups and semigroups. For this we introduce the notion of a distinguisher:…
Average Case Analysis of Leaf-Centric Binary Tree Sources
Louisa Seelbach Benkner, Markus Lohrey, Stephan Wagner
We study the average number of distinct fringe subtrees in random trees generated by leaf-centric binary tree sources as introduced by Zhang, Yang and Kieffer. A leaf-centric binar…
Exponent equations in HNN-extensions
Michael Figelius, Markus Lohrey
We consider exponent equations in finitely generated groups. These are equations, where the variables appear as exponents of group elements and take values from the natural numbers…
The complexity of knapsack problems in wreath products
Michael Figelius, Moses Ganardi, Markus Lohrey +1
We prove new complexity results for computational problems in certain wreath products of groups and (as an application) for free solvable group. For a finitely generated group we s…
Closure properties of knapsack semilinear groups
Michael Figelius, Markus Lohrey, Georg Zetzsche
We show that the following group constructions preserve the semilinearity of the solution sets for knapsack equations (equations of the form in a g…