{"ID":2835845,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.22212","arxiv_id":"2511.22212","title":"Balancing Two-Dimensional Straight-Line Programs","abstract":"We consider building, given a straight-line program (SLP) consisting of $g$ productions deriving a two-dimensional string $T$ of size $N\\times N$, a structure capable of providing random access to any character of $T$. For one-dimensional strings, it is now known how to build a structure of size $\\mathcal{O}(g)$ that provides random access in $\\mathcal{O}(\\log N)$ time. In fact, it is known that this can be obtained by building an equivalent SLP of size $\\mathcal{O}(g)$ and depth $\\mathcal{O}(\\log N)$ [Ganardi, Jeż, Lohrey, JACM 2021]. We consider the analogous question for two-dimensional strings: can we build an equivalent SLP of roughly the same size and small depth? We show that the answer is negative: there exists an infinite family of two-dimensional strings of size $N\\times N$ described by a 2D SLP of size $g$ such that any 2D SLP describing the same string of depth $\\mathcal{O}(\\log N)$ must be of size $Ω(g\\cdot N/\\log^{3}N)$. We complement this with an upper bound showing how to construct such a 2D SLP of size $\\mathcal{O}(g\\cdot N)$. Next, we observe that one can naturally define a generalization of 2D SLP, which we call 2D SLP with holes. We show that a known general balancing theorem by [Ganardi, Jeż, Lohrey, JACM 2021] immediately implies that, given a 2D SLP of size $g$ deriving a string of size $N\\times N$, we can construct a 2D SLP with holes of depth $\\mathcal{O}(\\log N)$ and size $\\mathcal{O}(g)$. This allows us to conclude that there is a structure of size $\\mathcal{O}(g)$ providing random access in $\\mathcal{O}(\\log N)$ time for such a 2D SLP. Further, this can be extended (analogously as for a 1D SLP) to obtain a structure of size $\\mathcal{O}(g \\log^εN)$ providing random access in $\\mathcal{O}(\\log N/\\log \\log N)$ time, for any $ε\u003e0$.","short_abstract":"We consider building, given a straight-line program (SLP) consisting of $g$ productions deriving a two-dimensional string $T$ of size $N\\times N$, a structure capable of providing random access to any character of $T$. For one-dimensional strings, it is now known how to build a structure of size $\\mathcal{O}(g)$ that p...","url_abs":"https://arxiv.org/abs/2511.22212","url_pdf":"https://arxiv.org/pdf/2511.22212v1","authors":"[\"Itai Boneh\",\"Estéban Gabory\",\"Paweł Gawrychowski\",\"Adam Górkiewicz\"]","published":"2025-11-27T08:30:43Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[\"Generative Adversarial Network\"]","has_code":false}