3 papers
cs.FL2026
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…
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…
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…