14 citations · 74 across the 41 of their papers we have counts for
64 papers
Compressed Subsequence Checking is PSPACE-complete
Markus Lohrey
It is shown that the (scattered) subsequence problem for two words represented by straight-line programs is -complete, even over a binary alphabet. The lower bound…
Low-Latency Sliding Window Algorithms for Formal Languages
Moses Ganardi, Louis Jachiet, Markus Lohrey +1
Low-latency sliding window algorithms for regular and context-free languages are studied, where latency refers to the worst-case time spent for a single window update or query. For…
Membership Problems in Finite Groups
Markus Lohrey, Andreas Rosowski, Georg Zetzsche
We show that the subset sum problem, the knapsack problem and the rational subset membership problem for permutation groups are NP-complete. Concerning the knapsack problem we obta…
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:…
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 Power Word Problem in Graph Products
Markus Lohrey, Florian Stober, Armin Weiß
The power word problem for a group asks whether an expression , where the are words over a finite set of generators of and the binar…