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 $ε>0$.

翻译：我们考虑在给定一个由g个产生式组成、推导出大小为N×N的二维字符串T的直线式程序（SLP）的情况下，构建一种能够提供对T中任意字符随机访问的结构。对于一维字符串，现已知道如何构建一个大小为O(g)的结构，在O(log N)时间内提供随机访问。事实上，已知这可以通过构建一个大小为O(g)、深度为O(log N)的等价SLP来实现[Ganardi, Jeż, Lohrey, JACM 2021]。我们考虑二维字符串的类似问题：能否构建一个大小大致相同且深度较小的等价SLP？我们证明答案是否定的：存在一个由大小为g的二维SLP描述的大小为N×N的二维字符串无限族，使得任何描述同一字符串且深度为O(log N)的二维SLP的大小必须为Ω(g·N/log³N)。我们通过一个上界来补充这一点，展示了如何构建一个大小为O(g·N)的此类二维SLP。接下来，我们观察到可以自然地定义二维SLP的推广，我们称之为带洞的二维SLP。我们证明，[Ganardi, Jeż, Lohrey, JACM 2021]中已知的一般平衡定理立即意味着，给定一个大小为g、推导大小为N×N的字符串的二维SLP，我们可以构建一个深度为O(log N)、大小为O(g)的带洞二维SLP。这使我们得出结论：存在一个大小为O(g)的结构，为此类二维SLP提供O(log N)时间内的随机访问。此外，这可以（类似于一维SLP）扩展为获得一个大小为O(g log^ε N)的结构，在O(log N/log log N)时间内提供随机访问，其中ε>0。