3 papers
cs.LO2025
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…
cs.DS2025
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…
cs.FL2024
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…