6 citations · 6 across the 3 of their papers we have counts for
4 papers
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…
Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems
Laurent Bartholdi, Michael Figelius, Markus Lohrey +1
We give lower bounds on the complexity of the word problem of certain non-solvable groups: for a large class of non-solvable infinite groups, including in particular free groups, G…