2026-07-20T05:05:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24176 2025-11-12T13:34:06Z ddc:004 open_access

FO-Query Enumeration over SLP-Compressed Structures of Bounded Degree Lohrey, Markus Maneth, Sebastian Schmid, Markus L. Enumeration algorithms FO-logic query evaluation over compressed data 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 this result towards the compressed perspective where the structure is given in a potentially highly compressed form by a straight-line program (SLP). Our main result is an algorithm that enumerates the result set of a first-order query over a structure of bounded degree that is represented by an SLP satisfying the so-called apex condition. For a fixed formula, the enumeration algorithm has constant delay and needs a preprocessing time that is linear in the size of the SLP. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Markus Lohrey and Sebastian Maneth and Markus L. Schmid 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.69 urn:nbn:de:0030-drops-241760 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.69 eng https://creativecommons.org/licenses/by/4.0/legalcode