4 papers
Word Length and Diameter in Permutation Groups
Markus Lohrey, Alexander Thumm
The input for the binary diameter problem consists of explicitly represented permutations generating a finite group and a binary-encoded nonnegative integer . The question i…
FO-Query Enumeration over SLP-Compressed Structures of Bounded Degree
Markus Lohrey, Sebastian Maneth, Markus L. Schmid
Enumerating the result set of a first-order query over a relational structure of bounded degree can be done with linear preprocessing and constant delay. In this work, we extend th…
Streaming algorithms for products of probabilities
Markus Lohrey, Leon Rische, Louisa Seelbach Benkner +1
We consider streaming algorithms for approximating a product of input probabilities up to multiplicative error of . It is shown that every randomized streaming algorithm for t…
MSO-Enumeration Over SLP-Compressed Unranked Forests
Markus Lohrey, Markus L. Schmid
We study the problem of enumerating the answers to a query formulated in monadic second order logic (MSO) over an unranked forest F that is compressed by a straight-line program (S…