2 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.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…