Dynamic direct (ranked) access of MSO query evaluation over SLP-compressed strings
Martín Muñoz · 2026
Read Dynamic direct (ranked) access of MSO query evaluation over SLP-compressed strings by Martín Muñoz (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-2603-13058.txt.
Introduction
Martín Muñoz presents an algorithm for ranked direct access to answers of MSO queries over strings. Given an index, it returns the answer at that spot in lexicographic order. Linear-time preprocessing builds a structure that answers each call in log time. The method extends to strings compressed by straight-line programs, with the same prep cost. Complex edits on the compressed form also update in log time. The access step beats a recent result by a log factor.
Catalog record
| CREATOR | Martín Muñoz |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62545 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.13058
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Dynamic direct (ranked) access of MSO query evaluation over SLP-compressed strings Martín Muñoz Abstract We present an algorithm that, given an index t t , produces the t t -th (lexicographically ordered) answer of an MSO query over a string. The algorithm requires linear-time preprocessing, and builds a data structure that answers each of these calls in logarithmic time. We then show how to extend this algorithm for a string that is compressed by a straight-line program (SLP), also with linear-time preprocessing in the (compressed encoding of the) string, and maintaining direct access in logtime of the original string. Lastly, we extend the algorithm by allowing complex edits on the SLP after the direct-access data structure has been processsed, which are translated into the data structure in logtime. We do this by adapting a document editing framework introduced by Schmid and Schweikardt (PODS 2022). This work improves on a recent result of dynamic direct access of MSO queries over strings (Bourhis et. al., ICDT 2025) by a log-factor on the access procedure, and by extending the results to SLPs. Univ. Artois, CNRS, UMR 8188, Centre de Recherche en Informatique de Lens (CRIL), F-62300, France [email protected] https://orcid.org/0009-0003-3294-6159 ccs Theory of computation Logic and databases ccs Theory of computation Data structures and algorithms for data management ccs Theory of computation Automata extensions keywords Direct Access, MSO, incremental evaluation, text compression, algorithms on compressed text † † runningtitle: Dynamic direct (ranked) access of MSO query eval. over SLP-compressed strings † † runningauthor: Martín Muñoz † † copyright: Martín Muñoz 1 Introduction Evaluating queries built from monadic-second order logic (MSO) formulas is a well-studied task in database theory and algorithmics for formal languages. A reason for this is that it serves as a pivot to other formalisms. In particular, owing to the Büchi-Elgot-Trakhtenbrot theorem [ 9 ] , it is known that MSO over words is equivalent to finite state automata and regular expressions. This equivalence also extends to trees, as MSO queries over trees are equivalent to tree regular languages and visibly pushdown automata. The reach of the task extends further, since the regex formulation means MSO evaluation has use in string processing; the tree formulation means it has use in XML processing; and very relevantly, MSO can be used to handle evaluation for regular spanners [ 14 , 7 , 23 ] . The base evaluation task is: given a MSO formula \varphi , a data string w , does w\models\varphi hold? (understanding w as an ordered monadic structure in the typical sense). A natural extension of this task is to instead query via a formula with open variables \varphi(x_{1},\ldots,x_{k}) , and to compute the assignments \mu such that w\models\varphi(\mu(x_{1}),\ldots,\mu(x_{k})) . Naturally, by this extension, the set of answers can become much larger than the input instance. To overcome this, a great deal of works have studied different ways of extracting the answers without producing them all at once. In MSO evaluation, we find works that explore the task of enumerating these answers one by one [ 3 , 12 , 1 ] ; we also find ranked enumeration , where the answers have to be produced in order [ 7 ] ; and direct access , where the set of answers is accessed on an arbitrary index [ 4 , 17 ] . We identify two different tasks that share a name in the literature. First is random access : for the set of answers S , the goal is to construct an index between 1 and |S| such that each produces a different answer from the set. Second is ranked access : the task is the same but there is an order on the answers, and the index follows this order. The naming in the literature shows discrepancies and both tasks have also been named direct access [ 11 , 8 , 10 , 5 ] . We highlight the fact that, as noted in [ 11 ] , direct random access can simulate uniform sampling and enumeration; whereas direct ranked access encompasses quantile queries (e.g., the median of the answers), ranked enumeration and top-k answering. On top of the evaluation task, some works venture into the realm of incremental evaluation . In other words, we allow changes in the data after it has been processed for the query. For MSO queries, this has been abundantly explored in enumeration [ 2 , 19 , 21 , 30 , 24 ] . However, as far as we know, only one work [ 6 ] has studied direct access for MSO on an editable string. The present work studies an algorithm for efficient direct ranked access on MSO queries. Further, we also consider a more complex setting: the string may have been compressed as a grammar with a singleton language [ 28 ] . Encodings of this form are typically called straight-line programs (SLP) [ 18 ] ; they enjoy good compression bounds and have enticing algorithmic properties [ 5 , 25 , 26 , 27 , 20 ] . Evaluation for MSO queries on SLP-compressed strings (and trees) has been already considered for enumeration [ 29 , 21 , 30 , 24 ] , yet we believe ours is the first work that approaches it from the angle of direct access. Background This work is an improvement of a result in [ 6 ] : an algorithm for dynamic direct access for MSO queries on strings. Their result achieves logsquare-access with log-updates on the size of the input string. In this work, we reduce the logsquare-access to a single log factor, maintaining the log-updates. Further, we include an extension to SLP-compressed strings which ends up appearing naturally due to the construction of the data structure. We borrow various concepts and insights from this work. Paper structure On Section 2 , we introduce some known concepts and easy extensions. On Section 3 , we present one of the main results of the paper, which is the direct access algorithm for MSO queries on strings. On Section 4 , we extend this result to SLPs, and on Section 5 , we explain how to handle edits. We give some closing words on Section 6 . Due to space constraints, we defer (at least one) proof to the appendix. Statements are given without proof when we believe they follow straightforwardly. 2 Preliminaries Let \mathbb{N}=\{0,1,\ldots\} . Given sets A,B we use the notation B^{A} for the set of functions f:A\to B . In particular, for a set A , we write \mathbb{N}^{A\times A} to denote the matrices of natural numbers indexed by pairs (a_{1},a_{2})\in A\times A . We also use the notation I_{A} for the A\times A identity matrix; i.e., I_{A}(a_{1},a_{2})=1 if a_{1}=a_{2} and I_{A}(a_{1},a_{2})=0 if a_{1}\neq a_{2} . We use [1,n]=\{1,\ldots,n\} . We use the symbol < to denote the standard order over \mathbb{N} . If a set A is totally ordered by some order \preccurlyeq , we will use the word slice for a subset B\subseteq A that can be described by two elements a_{l},a_{r}\in A such that B=\{a\mid a_{l}\preccurlyeq a\preccurlyeq a_{r}\} . We write \omega<3 for an exponent for binary matrix multiplication [ 31 ] . Strings and mappings Given a finite