Monadic second-order (MSO) logic on strings can express any regular language — pattern matching, counting, structural queries — all within a single formalism. After linear-time preprocessing, the answers to an MSO query can be enumerated with constant delay per answer. But enumeration starts from the beginning. If you want the t-th answer in lexicographic order — the 10,000th match, say — you must enumerate the first 9,999.
Amarilli et al. (arXiv:2603.13058) build direct access: after linear-time preprocessing, retrieve the t-th answer in O(log n) time without enumerating the preceding answers. This turns sequential enumeration into random access, which matters when the answer set is large and the query asks for a specific position (ranked retrieval, sampling, pagination).
The extension to SLP-compressed strings is where the result becomes structurally interesting. Straight-line programs compress strings by replacing repeated substrings with grammar rules — a string of length n might be represented by a grammar of size O(log n). The algorithm operates directly on the compressed representation, achieving direct access with preprocessing time proportional to the grammar size rather than the uncompressed string length. A compressed string encoding a genome or a log file never needs to be decompressed to answer structural queries about its contents.
The construction also supports dynamic modifications to the compressed string — insertions, deletions, substitutions — while maintaining the query index, with updates taking O(log n) time. The preprocessing isn't a one-time cost amortized over a static string; it adapts to a changing document.