Ranked MSO-enumeration over compressed words

Markus Lohrey · 2026

Read Ranked MSO-enumeration over compressed words by Markus Lohrey (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-03947.txt.

Introduction

Lohrey studies ranked query listing over compressed strings. The input string comes from a straight-line program, a grammar that yields just one string. Queries are fixed in monadic second-order logic. Ranked means the answers must print in a set order. That order itself must be definable in the same logic. No prior result covered ranked listing on compressed data.

Lohrey shows the task allows linear preprocessing and constant delay per answer. A corollary covers listing the symbols of a transformed word in order. It extends a known result for plain, uncompressed words. The proofs rest on factorization trees. Making those trees work in the compressed setting is a gain on its own, he notes.

Catalog record

CREATORMarkus Lohrey
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE101 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.03947

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Ranked MSO-enumeration over compressed words Markus Lohrey Abstract It is shown that the ranked query enumeration problem for a fixed MSO-query on strings can be solved with linear preprocessing and constant delay in the grammar-compressed setting, where the input string is given by a so-called straight-line program, i.e., a context-free grammar that produces exactly one string. Moreover, ‘ranked’ means that the output tuples of the MSO-query are printed in a specific order that has to be MSO-definable. This is the first result for ranked query enumeration on compressed data. A corollary of this result is that for a fixed polyregular function f f and a word w w that is given by a straight-line program of size n n , one can list after preprocessing time 𝒪 ⁡ ( n ) \mathcal{O}(n) the symbols in f ⁡ ( w ) f(w) from left to right with constant delay, which generalizes a result of Bojanczyk for the case where w w is uncompressed. The proofs for these results are based on factorization trees, which are made accessible to the grammar-compressed setting (a contribution of independent interest). Universität Siegen, [email protected]://orcid.org/0000-0002-4680-7198 ccs Theory of computation Database query processing and optimization (theory) keywords monadic second-order queries, enumeration algorithms, grammar compression, factorization trees † † runningauthor: M. Lohrey 1 Introduction The evaluation of queries formulated in monadic second order logic (MSO) is a classical problem in database theory and finite model theory. If we allow arbitrary structures, then already the model-checking problem for MSO (and even first-order logic) is PSPACE -complete. Here, the input consists of the structure and the formula. In real applications from data base theory or verification, the structure can be huge whereas the formula is often small. This motivates the study of data complexity , where the formula is fixed and not part of the input. Still, MSO-model-checking is hard for all levels of the polynomial time hierarchy with respect to data complexity. In order to get efficient algorithms, one has to restrict the class of allowed input structures. A famous result in this context is Courcelle’s meta-theorem [ 13 ] , saying that the data complexity of MSO-model-checking is linear time on the class of all structures of treewidth at most k (for every fixed k ). In this paper, we will only consider data complexity. The model-checking problem for MSO is the same as the evaluation problem for boolean MSO-queries. In data base theory, one is usually interested in queries with free variables and the computation of all query answers. Here, we consider MSO-queries \Phi(x_{1},\ldots,x_{k}) with free first-order variables x_{i} . The goal is then to compute all tuples (a_{1},\ldots,a_{k}) in an input structure \mathcal{A} (that models the input data) such that \mathcal{A}\models\Phi(a_{1},\ldots,a_{k}) holds. The number of these tuples is clearly bounded by |\mathcal{A}|^{k} which can be very large in applications, where the input data are large. In order to have a reasonable notion of efficient algorithms for computing query answers, the concept of enumeration algorithms has been introduced. Such an algorithm starts for a given input structure \mathcal{A} with a preprocessing phase building a suitable data structure for the enumeration phase that starts right after the preprocessing phase. In the enumeration phase the algorithm computes all tuples (a_{1},\ldots,a_{k}) satisfying the (fixed) MSO-query \Phi(x_{1},\ldots,x_{k}) without producing a tuple twice. The gold standard for the efficiency of an enumeration algorithm is a linear preprocessing time \mathcal{O}(|\mathcal{A}|) and constant delay , where the latter means that there is a constant bounding the following computation times: (i) the time for computing the first output tuple, (ii) the time between outputting two tuples, and (iii) the time between outputting the last tuple and final termination. Note that constant delay makes only sense for data complexity since otherwise the length k of the tuples would not be fixed. Moreover constant delay assumes that every element of the input structure \mathcal{A} fits into constantly many output registers. Note that in the above setting, the MSO-formula only contains free first-order formulas. One may also allow queries \Phi(x_{1},\ldots,x_{k},X_{1},\ldots,X_{l}) with free set variable X_{i} . Although this is not the focus of the paper, we mention it because some of the related papers cited below consider this more general setting. Clearly, the output tuples then no longer fit into constant space and therefore cannot be printed in constant time. The best possible delay bound is then output-linear delay , meaning that the delay for printing an output tuple is linearly bounded in the size of the tuple. For a fixed query \Phi(x_{1},\ldots,x_{k}) containing only free first-order variables, output-linear delay is equivalent to constant delay. Enumeration algorithms with linear preprocessing and constant delay or output-linear delay are known for several classes of queries and structures, including MSO-queries on strings, trees and structures with bounded treewidth [ 3 , 5 , 14 , 21 , 22 , 31 , 32 ] and for regular document spanners (which is a subclass of MSO-queries) on strings [ 4 , 15 ] . As mentioned above, the input structure for query evaluation can be huge in applications. This has motivated the investigation of query enumeration algorithms for structures that are given in a compressed form. The compression format that has been studied so far in the context of query enumeration is grammar-compression . For strings this means that the input string is given by a context-free grammar that produces exactly one string. Such grammars are also known as straight-line algorithm (SLP for short) and have received a lot of attention in data compression, information theory, stringology and even areas like computational topology and group theory; see the survey [ 24 ] for more details. In data base theory, query enumeration algorithms on compressed structures have been first studied in the context of strings and document spanners [ 34 , 35 , 36 ] . This work has been extended to full MSO in [ 29 ] , where it is shown that for a fixed MSO-query and a given input word that is represented by an SLP \mathcal{G} , the set of all query answers can be enumerated with linear processing (meaning time \mathcal{O}(|\mathcal{G}|) where |\mathcal{G}| is the size of the SLP \mathcal{G} ) and output-linear delay (the authors of [ 29 ] consider MSO-formulas with free set variables). In [ 28 ] this result has been extended to unranked trees that are given by so-called forest straight-line programs [ 17 ] (an extension of SLPs that allows to compress unranked trees), whereas [ 27 ] goes one step further to grammar-compressed graphs of bounded degree but restricts to queries expressed in first-order logic. A drawback in all the above mentioned results on query answer enumeration is the fact that the output tuples are printed in some opaque order that cannot be controlled by the user. To overcome this drawback, researchers have developed the concept of ranked enumeration, where the output tuples are printed in a specific order that can be specified in a suitable formalism. Ranked enumeration for MSO-queries has been considered in [ 12 , 19 ] for strings and [ 2 ] for trees. In [ 12 , 19 ] , query answers are enumerated in the order of decreasing

Read the complete text