14 citations · 74 across the 41 of their papers we have counts for
6 papers · 1 filter
Compressed decision problems in hyperbolic groups
Derek Holt, Markus Lohrey, Saul Schleimer
We prove that the compressed word problem and the compressed simultaneous conjugacy problem are solvable in polynomial time in hyperbolic groups. In such problems, group elements a…
Knapsack in hyperbolic groups
Markus Lohrey
Recently knapsack problems have been generalized from the integers to arbitrary finitely generated groups. The knapsack problem for a finitely generated group is the following…
The Complexity of Bisimulation and Simulation on Finite Systems
Moses Ganardi, Stefan Göller, Markus Lohrey
In this paper the computational complexity of the (bi)simulation problem over restricted graph classes is studied. For trees given as pointer structures or terms the (bi)simulation…
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…
Randomized sliding window algorithms for regular languages
Moses Ganardi, Danny Hucke, Markus Lohrey
A sliding window algorithm receives a stream of symbols and has to output at each time instant a certain value which only depends on the last symbols. If the algorithm is rando…
Grammar-based Compression of Unranked Trees
Adrià Gascón, Markus Lohrey, Sebastian Maneth +2
We introduce forest straight-line programs (FSLPs) as a compressed representation of unranked ordered node-labelled trees. FSLPs are based on the operations of forest algebra and g…