{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreigx7uxv4op56wsr2iewohtr6qnvd3shkl5ecpgfgc3vgr3z3uzn5m",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mnesqq5gjpi2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.03947v1",
  "publishedAt": "2026-06-03T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Markus Lohrey"
  ],
  "textContent": "**Authors:** Markus Lohrey\n\nIt 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$ and a word $w$ that is given by a straight-line program of size $n$, one can list after preprocessing time $\\mathcal{O}(n)$ the symbols in $f(w)$ from left to right with constant delay, which generalizes a result of Bojanczyk for the case where $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).",
  "title": "Ranked MSO-enumeration over compressed words"
}