FO-Query Enumeration over SLP-Compressed Structures of Bounded Degree
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908419142713344 |
|---|---|
| author | Lohrey, Markus Maneth, Sebastian Schmid, Markus L. |
| author_facet | Lohrey, Markus Maneth, Sebastian Schmid, Markus L. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_19421 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | FO-Query Enumeration over SLP-Compressed Structures of Bounded Degree Lohrey, Markus Maneth, Sebastian Schmid, Markus L. Logic in Computer Science 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. |
| title | FO-Query Enumeration over SLP-Compressed Structures of Bounded Degree |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2506.19421 |