Balancing Two-Dimensional Straight-Line Programs

We study the problem of balancing 2D SLPs. Our first result is a simple upper bound, showing that given a 2D SLP of size $g$ deriving a string of size $N\times M$ (for $N\ge M$) we can construct a 2D SLP of size $𝒪(g\cdot M)$ and depth $𝒪(\log N)$. This is, of course, a significant increase in the size for highly compressible strings. A natural question is whether we could, similarly to 1D SLPs, achieve the same balancing without increasing the SLP size. Namely, given a 2D SLP on $g$ productions deriving a string of size $N\times M$ (for $N\ge M$), is there a 2D SLP on $𝒪(g)$ productions deriving the same string but of depth $𝒪(\log N)$? We give a negative answer to this question, showing that for infinitely many values of $N$ there exists an $N\times N$ 2D string described by a 2D SLP of size $g$, such that any 2D SLP of depth $𝒪(\log N)$ describing the same string must consist of $\mathrm{\Omega }(g\cdot N/{\log }^{3}N)$ productions.

To overcome this barrier, we define a natural generalization of 2D SLPs: 2D SLPs with holes. In such a SLP, a nonterminal can also derive a 2D string from which a rectangular fragment has been removed. One can then naturally define the productions as either horizontal or vertical concatenations of two nonterminals in which at most one has a hole, and substituting the string (with or without a hole) derived by a nonterminal into the hole of the string derived by another nonterminal, see Figure 1. Then, given a 2D SLP with holes of depth $d$, we can implement random access in $𝒪(d)$ time by simply storing, for every nonterminal, the size of its derived string together with the position of its hole (if one exists). Now, given a 2D SLP of size $g$ deriving a 2D string of size $N\times M$ (for $N\ge M$), we would like to construct a balanced 2D SLP with holes deriving exactly the same string. We observe that the general balancing theorem of Ganardi, Jeż, and Lohrey [14] immediately implies that one can obtain such a 2D SLP with holes of size $𝒪(g)$ and depth $𝒪(\log N)$. Next, by “unwinding” the first $\mathrm{\Theta }(\log \log N)$ levels of the derivation of each nonterminal, this allows us to obtain a structure of size $𝒪(g\cdot {\log }^{ϵ}N)$ and query time $𝒪(\log N/\log \log N)$, for any $ϵ>0$, in the Word RAM model. Such query time is optimal for structures of size $𝒪(g\mathrm{polylog}N)$ by applying the lower bound for 1D SLPs, and our space is smaller by two factors of $\log N$ compared to the recent result of De and Kempa [11], matching the best known bounds for 1D SLPs [3].

For integers $i,j$, we denote $[i..j]=\{i,i+1,\mathrm{\dots },j\}$ ($[i..j]=\mathrm{\varnothing }$ for ), and $[i]=[1..i]$. We also denote $(i-1..j+1)=[i..j+1)=(i-1..j]=[i..j]$.

Let $\mathrm{\Sigma }$ be a fixed finite alphabet. A string $S=S[1]S[2]\mathrm{\dots }S[N]$ of length $N$ is a sequence of $N$ characters from $\mathrm{\Sigma }$. For $i,j\in [N]$, we define a substring $X$ of $S$ as $X=S[i..j]=S[i]S[i+1]\mathrm{\dots }S[j]$. If $i=1$ or $j=N$, the substring $X$ is called a prefix or a suffix of $S$, respectively.

An $N\times M$ two-dimensional (2D) string $S$ is an $N\times M$ array of characters from $\mathrm{\Sigma }$. We write $\mathrm{h}(S)$ to denote the number of rows $N$, and $\mathrm{w}(S)$ to denote the number of columns $M$. We also write $dim(S)$ to denote the pair $(N,M)$. Similarly to 1D strings, we define a substring of $S$ as $X=S[i..j][i^{\prime }..j^{\prime }]$ for some $i,j\in [N]$ and $i^{\prime },j^{\prime }\in [M]$. For every $i\in [N]$, we define $S[i]=S[i][1..M]$ as the $i$-th row of $S$. We observe that $S[i]$ is a string. Given two 2D strings $A$, $B$, we define their horizontal concatenation $A\ominus B$ when $\mathrm{h}(A)=\mathrm{h}(B)$ and their vertical concatenation $A\ominus B$ when $\mathrm{w}(A)=\mathrm{w}(B)$ in the natural way. We sometimes interchangeably view one-dimensional (1D) strings of length $N$ as $1\times N$ strings, and elements of $\mathrm{\Sigma }$ as $1\times 1$ strings. For a more detailed introduction on 2D strings and languages, see [16].

A 2D straight-line program $𝒢$ is a grammar $(𝒱,𝒮,\rho )$ where:

• $\mathrm{■}$

  $𝒱$ is a set of nonterminals, with $𝒱\cap \mathrm{\Sigma }=\mathrm{\varnothing }$. Each $X\in 𝒱$ has a dimension $dim(X)=(\mathrm{h}(X),\mathrm{w}(X))$ indicating that it derives a string of size $\mathrm{h}(X)\times \mathrm{w}(X)$.

• $\mathrm{■}$

  $𝒮\in 𝒱$ is called the starting nonterminal.

• $\mathrm{■}$

  $\rho$ is a mapping on the set $𝒱$, where $\rho (X)$ is one of the following:

  • –

    $\sigma$, where $\sigma \in \mathrm{\Sigma }$, and $\mathrm{h}(X)=\mathrm{w}(X)=1$,

  • –

    $Y\ominus Z$, where $Y,Z\in 𝒱$, $\mathrm{h}(X)=\mathrm{h}(Y)=\mathrm{h}(Z)$, $\mathrm{w}(X)=\mathrm{w}(Y)+\mathrm{w}(Z)$,

  • –

    $Y\ominus Z$, where $Y,Z\in 𝒱$, $\mathrm{w}(X)=\mathrm{w}(Y)=\mathrm{w}(Z)$, $\mathrm{h}(X)=\mathrm{h}(Y)+\mathrm{h}(Z)$.

  We call the pair $(X,\rho (X))$ a production, with $X$ being its left-hand side and $\rho (X)$ its right-hand side. We require that the relation on $𝒱$ defined by $X\le Y$ if $Y$ appears in the right-hand side of $X$ must be acyclic. We will sometimes allow a production $\rho (X)$ to be any string over $\mathrm{\Sigma }\cup 𝒱$, and then normalize the grammar in the standard way.

From the acyclicity condition, it follows that for each nonterminal $X\in 𝒱$, there is a unique 2D string ${\mathrm{Exp}}_{𝒢}(X)$ (or simply $\mathrm{Exp}(X)$ if $𝒢$ is clear from the context), called the expansion of $X$, derived from $X$ by recursively replacing each nonterminal in the right-hand side of its production by the corresponding derived string. This process can be described as a tree ${𝒯}_{𝒢}$, called the derivation tree of $𝒢$. Every internal node in ${𝒯}_{𝒢}$ is labeled with a nonterminal of $𝒢$, while each leaf is labeled with a symbol from $\mathrm{\Sigma }$. The root corresponds to the starting nonterminal $𝒮$. The children of a node labeled with a nonterminal $X\in 𝒱$ correspond to the nonterminals that appear in $\rho (X)$, or a letter $\sigma \in \mathrm{\Sigma }$ if $\rho (X)=\sigma$.

The 2D string derived by the SLP is denoted by $\mathrm{Exp}(𝒢)={\mathrm{Exp}}_{𝒢}(𝒮)$. The size $|𝒢|$ is the total number of symbols on the right-hand sides of all productions, and the depth of $𝒢$ is the depth of ${𝒯}_{𝒢}$. Notice that there is a 1-1 correspondence between the leaves of ${𝒯}_{𝒢}$ and the positions in $\mathrm{Exp}(𝒢)$.

We view one-dimensional SLPs as a special case of 2D SLPs that use only horizontal concatenations and derive strings of height $1$.

For efficient random access on 2D strings, we need predecessor queries and fusion trees. Let $S\subseteq [U]$ be a set of integers. A predecessor query on $S$ takes as input an integer $x\in [U]$ and returns the largest integer $y\in S$ such that $y\le x$. We have the following result in the Word RAM model.

Let $𝒢=(𝒱,𝒮,\rho )$ be the given grammar. For each $X\in 𝒱$ we introduce nonterminals $X_1,X_2,\mathrm{\dots },X_{\mathrm{h}(X)}$. The goal is to construct a 1D SLP ${𝒢}^{\prime }=({𝒱}^{\prime },{𝒮}^{\prime },{\rho }^{\prime })$ over all the introduced nonterminals, so that for every $X\in 𝒱$ and $i\in [\mathrm{h}(X)]$ we have

We first set ${𝒱}^{\prime }≔\{X_i:X\in 𝒱,i\in [\mathrm{h}(X)]\}\cup \left\{{𝒮}^{\prime }\right\}$, where ${𝒮}^{\prime }$ is a new starting nonterminal. Since each nonterminal $X$ introduces at most $\mathrm{h}(X)\le N$ new nonterminals, we have $|{𝒱}^{\prime }|=𝒪(|𝒱|\cdot N)$. The productions ${\rho }^{\prime }(X_i)$ are defined depending on the production $\rho (X)$:

1. 1.

   if $\rho (X)=\sigma \in \mathrm{\Sigma }$, then ${\rho }^{\prime }(X_1)≔\sigma$,

2. 2.

   if $\rho (X)=A\ominus B$, then ${\rho }^{\prime }(X_i)≔A_i\ominus B_i$,

3. 3.

   if $\rho (X)=A\ominus B$ and $i\le \mathrm{h}(A)$, then ${\rho }^{\prime }(X_i)≔A_i$,

4. 4.

   if $\rho (X)=A\ominus B$ and $i>\mathrm{h}(A)$, then ${\rho }^{\prime }(X_i)≔B_{i-\mathrm{h}(A)}$.

To define ${\rho }^{\prime }({𝒮}^{\prime })$ as the horizontal concatenation of ${𝒮}_1,{𝒮}_2,\mathrm{\dots },{𝒮}_N$, we use the concatenation gadget (Proposition 3), adding $𝒪(N)$ to the overall size of ${𝒢}^{\prime }$. It follows by induction that for every $X\in 𝒱$ and $i\in [\mathrm{h}(X)]$, ${\mathrm{Exp}}_{{𝒢}^{\prime }}(X_i)={\mathrm{Exp}}_{𝒢}(X)[i]$, and thus ${\mathrm{Exp}}_{{𝒢}^{\prime }}({𝒮}^{\prime })=T[1]\ominus T[2]\ominus \mathrm{\cdots }\ominus T[N]$. $◀$

We now proceed with the proof of Theorem 2. Let $𝒢$ be a 2D SLP deriving a string $T$ of size $N\times M$ (for $N\le M$). We apply Lemma 4 and then balance the resulting 1D SLP.

We obtain a 1D SLP ${𝒢}^{\prime }=({𝒱}^{\prime },{𝒮}^{\prime },{\rho }^{\prime })$ of size $𝒪(|𝒢|\cdot N)$ and depth $𝒪(\log M)$, deriving

We view ${𝒢}^{\prime }$ as a 2D SLP that uses only horizontal concatenations. We will now modify it, so that it again derives the original 2D string $T$ while maintaining its logarithmic depth.

Take any substring from position $i$ to $j$. In the derivation tree of $\mathscr{H}$ let $u$ be the lowest common ancestor of the $i$-th and $j$-th leaf. Along the two root-to-leaf paths from $u$, take the siblings hanging to the right of the left path and to the left of the right path, together with the $i$-th and the $j$-th leaf. The concatenation of these $𝒪(d)$ nonterminals expands to the whole substring. $◀$

Since every row $T[i]$ is a substring of $\mathrm{Exp}({𝒢}^{\prime })$, we can use Lemma 6 to identify $𝒪(\log M)$ nonterminals $X_1,X_2,\mathrm{\dots },X_k$, such that

Then, for each $i$, we introduce a new nonterminal $R_i$ by applying Proposition 3 to $X_1,\mathrm{\dots },X_k$, implementing the production

Each gadget increases the depth by $𝒪(\log \log M)$ and creates $𝒪(\log M)$ new symbols, but since the $R_i$’s are created independently (none of them occurs in another’s subtree), the overall depth of the grammar increases by only $𝒪(\log \log M)$ altogether. The total increase in size is $𝒪(N\log M)$, which is $𝒪(|𝒢|\cdot N)$, because of the straightforward lower bound of $\mathrm{\Omega }(\log M)$ on the size of $𝒢$.

Finally, we introduce a new starting nonterminal ${𝒮}^{\prime \prime }$ with the production

constructed using Proposition 3, adding $𝒪(N)$ to the size and $𝒪(\log N)$ to the depth of ${𝒢}^{\prime }$. Then

The resulting grammar has size $𝒪(|𝒢|\cdot N)$, and depth $𝒪(\log M)$.

Observe that the string $R_{N,i}$ contains substrings of the form $\$b\$$ where $b$ is the $\log N$-bit binary encoding of some number $z_b$. Specifically, $R_{N,i}$ contains such substrings for $\min \{i,2N-i+1\}$ distinct values of $z_b$.

Let $𝒢$ be a grammar deriving a superstring of $R_{N,i}$. For every $z_b$ such that $\$b\$$ is a substring of $R_{N,i}$, denote as $A(z_b)$ the minimal nonterminal of $𝒢$ that expands to a superstring of $\$b\$$. That is, $A(z_b)$ is a nonterminal expanding to a string containing $\$b\$$ as a substring, with rule $\rho (A(z_b))=B\ominus C$ such that neither $B$ nor $C$ contains $\$b\$$ as a substring.

We claim that for every two distinct $z_b,z_{b^{\prime }}$, it holds that $A(z_b)\ne A(z_{b^{\prime }})$. Indeed, $\rho (A(z_b))=B\ominus C$ such that $\mathrm{Exp}(B)$ has a suffix of the form $\$b_1$ and $\mathrm{Exp}(C)$ has a prefix of the form $b_2\$$ satisfying $b=b_1\cdot b_2$. Similarly, $\rho (A(z_{b^{\prime }}))=B^{\prime }\cdot C^{\prime }$ such that $B^{\prime }$ has suffix $\$b_1^{\prime }$ and $C^{\prime }$ has prefix $b_2^{\prime }\$$ satisfying $b^{\prime }=b_1^{\prime }\ominus b_2^{\prime }$. Since $b\ne b^{\prime }$ and $\$$ does not occur in $b$ or $b^{\prime }$, it cannot be the case that $A(z_b)=A(z_{b^{\prime }})$. We have shown that $𝒢$ contains a distinct nonterminal for every one of the $\min \{i,2N-i+1\}$ different values of $z_b$, which concludes the proof. $◀$

Next, we show that a 2D grammar deriving a string $S$ implies a 1D grammar of similar size deriving the margins of $S$.

We show how to construct a grammar for $t$, the remaining cases are symmetric.

We create 1D SLP ${𝒢}^{\prime }$ with nonterminals ${𝒱}^{\prime }=\{A^{\prime }:A\in 𝒱\}$. For every nonterminal $A\in 𝒱$, if $\rho (A)=B\ominus C$, we set $\rho (A^{\prime })≔B^{\prime }$ (i.e., keeping just the top part of $\mathrm{Exp}(A)$). If $\rho (A)=B\ominus C$, we set $\rho (A^{\prime })≔B^{\prime }\ominus C^{\prime }$. If $\rho (A)=\sigma$ for some terminal $\sigma$, we set $\rho (A^{\prime })≔\sigma$.

It is clear that $|{𝒢}^{\prime }|\le |𝒢|$, and it can be verified (for example, by induction) that ${𝒢}^{\prime }$ derives the top row of $S$, as required. $◀$

Let us define the main gadget used for proving Theorem 7.

Recall that the width of ${\mathrm{𝖲𝗁𝗂𝖿𝗍𝖡𝗂𝗇}}_{M^{\prime }}$ is $M^{\prime }(\log M^{\prime }+2)$. Therefore, the width of each vertical block is $M^{\prime }(\log M^{\prime }+2)\le M/2$, so the combined width of the first two blocks never exceeds $M$. Also recall that the height of ${\mathrm{𝖲𝗁𝗂𝖿𝗍𝖡𝗂𝗇}}_{M^{\prime }}$ is $2M^{\prime }$, so each block contains the maximal number of vertically concatenated copies of ${\mathrm{𝖲𝗁𝗂𝖿𝗍𝖡𝗂𝗇}}_{M^{\prime }}$ that fit within height $N$ (for the right block, this takes into account the initial vertical shift of $M^{\prime }$ positions).

We proceed to show that there is a logarithmic sized 2D SLP deriving $C_{N,M}$.

Each of the two blocks of $C_{N,M}$ can be produced by starting with a grammar of size $𝒪(\log M)$ that derives $B$, and adding $𝒪(\log (N/M))$ nonterminals that produce concatenations of exponentially increasing amounts of $B$. Then, to get a block of $C_{N,M}$ we can concatenate $𝒪(\log (N/M))$ such nonterminals. The $0$ paddings can be obtained using additional $𝒪(\log N+\log M)$ nonterminals. $◀$

In our lower bound construction, we are interested in constructing a grammar with nonterminals producing a sequence of $k+1$ gadgets of the form

for some $b$ that is an integer multiple of $M^{\prime }$. In the following lemma, we show that nonterminals producing such sequence can be constructed using a small amount of additional nonterminals.

We will show how to construct a grammar with the required amount of nonterminals, containing $C_i$ for even values of $i$. A similar grammar can be constructed for odd values of $i$, and the union of the two grammars satisfies the required conditions. For an integer $N^{\prime }$, we denote the following substrings of $C_{N^{\prime },M}$:

1. 1.

   $B_{N^{\prime }}^1$ is the left vertical block of $C_{N^{\prime },M}$, without the vertical padding to complement the height to $N$.

2. 2.

   $B_{N^{\prime }}^2$ is defined identically to $B_{N^{\prime }}^1$, but for the right block of $C_{N^{\prime },M}$.

3. 3.

   $B_{N^{\prime }}^3$ is the horizontal padding to complement the width of $C_{N^{\prime },M}$ to $M$.

4. 4.

   $P_{N^{\prime }}^1$ is the vertical padding at the bottom of the left vertical block.

5. 5.

   $P_{N^{\prime }}^2$ is the vertical padding at the bottom of the right vertical block.

We observe that $P_N^1$ and $P_N^2$ are all-$0$s strings, and their dimensions depend only on the remainder of $N$ modulo $2M^{\prime }$. Therefore, $P_N^1=P_{N+2b}^1$ and $P_N^2=P_{N+2b}^2$. We also observe that $B_{N+2b}^1$ is obtained from $B_N^1$ by appending $b/M^{\prime }$ copies of ${\mathrm{𝖲𝗁𝗂𝖿𝗍𝖡𝗂𝗇}}_{M^{\prime }}$ to the bottom of $B_N^1$, and the same is true for $B_N^2$ and $B_{N+2b}^2$. Finally, $B_{N+2b}^3$ is obtained from $B_N^3$ by appending a block of $0$’s with height $2b$ and appropriate width.

Let ${𝒢}_{N,M}$ be the grammar deriving $C_{N,M}$ as described in Lemma 13. Recall that the grammar ${𝒢}_{N,M}$ has nonterminals generating each of $B_N^1$, $B_N^2$, $B_N^3$, $P_N^1$ and $P_N^2$. We extend ${𝒢}_{N,M}$ to include the following nonterminals:

1. 1.

   $V_1^{\prime }$: a vertical concatenation of $b/M^{\prime }$ copies of ${\mathrm{𝖲𝗁𝗂𝖿𝗍𝖡𝗂𝗇}}_{M^{\prime }}$.

2. 2.

   $V_2^{\prime }$: an all-$0$s block with height $2b$ and width $w(B_N^3)$.

Observe that both $V_1^{\prime }$ and $V_2^{\prime }$ can be added to the grammar using $𝒪(\log N+\log M)$ additional nonterminals. It follows from the above discussion that if we have a grammar with nonterminals expanding to $B_{N^{\prime }}^1$, $B_{N^{\prime }}^2$, $B_{N^{\prime }}^3$, $P_{N^{\prime }}^1$ and $P_{N^{\prime }}^2$, we can add $𝒪(1)$ nonterminals to obtain nonterminals expanding to $B_{N^{\prime }+2b}^1$, $B_{N^{\prime }+2b}^2$, $B_{N^{\prime }+2b}^3$, $P_{N^{\prime }+2b}^1$, and $P_{N^{\prime }+2b}^2$. Then, a nonterminal $C_{N^{\prime }+2b}$ can be added by adding additional $𝒪(1)$ nonterminals concatenating the above appropriately. By repeating this process $\lfloor k/2\rfloor$ times, we obtain a grammar containing $C_{N+i\cdot b,M}$ for every even $i$ in $[0..k]$. The total number of nonterminals is $𝒪(\log N+\log M+k)$, as required. $◀$

We are now ready to prove Theorem 7.

Let us start by providing some intuition. We will construct a string $S$ that is composed of instances of $C_{N^{\prime },M^{\prime }}$ with $M^{\prime }\in \mathrm{\Theta }(\frac{N}{\log N})$. The instances are nested in a spiral manner with decreasing lengths (see Figure 4). The ’depth’ of this spiral (i.e., number of swirls before the center is reached) will be roughly $c\log N$. Since every ’step’ in this pattern is a $C_{N^{\prime },M^{\prime }}$ gadget with $N^{\prime },M^{\prime }\in 𝒪(N)$, a grammar $𝒢$ deriving $S$ can be easily constructed using $𝒪({\log }^{2}N)$ nonterminals. We will actually show how to construct such a grammar with $𝒪(\log N)$ nonterminals.

To understand the intuition behind this construction, think of a 2D SLP ${𝒢}^{\prime }$ deriving $S$ with a small number of nonterminals (i. e. , $|{𝒢}^{\prime }|\in o(\frac{N}{{\log }^{2}N})$ ). Think of a path $P$ in the derivation tree of ${𝒢}^{\prime }$ from the root to some index at the center of $S$. It is helpful to think of $P$ as a sequence of nested rectangles in $S$, all containing the center point of $S$. Intuitively, each of the $C_{N^{\prime },M^{\prime }}$ gadgets limits the structure of these rectangles. Namely, these rectangles cannot horizontally intersect a $C_{N^{\prime },M^{\prime }}$ gadget (except possibly very close to the top/bottom of said gadget), as this would imply that the top/bottom of a rectangle contains some row of a $\mathrm{𝖲𝗁𝗂𝖿𝗍𝖡𝗂𝗇}$ gadget as a substring. By Lemma 10 and Lemma 11, a nonterminal that expands to a string with such a top/bottom row requires a large number of nonterminals, contradicting the small size of ${𝒢}^{\prime }$. It follows that the rectangles of $P$ have to roughly comply with the structure of the spiral. This allows us to lower bound $|P|$, and thus the depth of ${𝒢}^{\prime }$.

We proceed to define $𝒢$ and $S$. Let ${\mathrm{\Delta }}^{\prime }=\frac{N}{8c\log N}$ and $\lambda =2c\log N$. Let $M^{\prime }$ be the largest power of $2$ such that $M^{\prime }(\log M^{\prime }+2)\le {\mathrm{\Delta }}^{\prime }/2$. Let $\mathrm{\Delta }$ be the largest integer smaller than ${\mathrm{\Delta }}^{\prime }$ that is an integer multiple of $M^{\prime }$. Notice that we must have $\mathrm{\Delta }\in [{\mathrm{\Delta }}^{\prime }/2..{\mathrm{\Delta }}^{\prime }]$ since ${\mathrm{\Delta }}^{\prime }\ge 2M^{\prime }$ and $\mathrm{\Delta }\ge {\mathrm{\Delta }}^{\prime }-M^{\prime }$. Also observe that $M^{\prime \prime }$, the largest power of two such that $M^{\prime \prime }(\log M^{\prime \prime }+2)\le \mathrm{\Delta }$, must be exactly $M^{\prime \prime }=M^{\prime }$ (otherwise, $2M^{\prime }(\log M^{\prime }+2)$ is an integer multiple of $M^{\prime }$ strictly between ${\mathrm{\Delta }}^{\prime }$ and $\mathrm{\Delta }$).

For an integer $N^{\prime }\in \mathbb{N}$, let ${\tilde{C}}_{N^{\prime },\mathrm{\Delta }}$ denote the string $C_{N^{\prime },\mathrm{\Delta }}$ rotated clockwise by $90$ degrees. We denote as $G(N^{\prime })$ and $\tilde{G}(N^{\prime })$ the nonterminals that expand to $C_{N^{\prime },\mathrm{\Delta }}$ and ${\tilde{C}}_{N^{\prime },\mathrm{\Delta }}$, respectively.

We define the SLP $𝒢=(𝒱,F_0^0,\rho )$ as follows. For every $i\in [0..\lambda -1]$ and $x\in \{0,1,2,3\}$ there is a nonterminal $F_i^x$ in $𝒱$ with the following derivation rules (see Figure 4 for a demonstration):

1. 1.

   $\rho (F_i^0)≔F_i^1\ominus G(N-2i\cdot \mathrm{\Delta })$ for every $i\in [0..\lambda -1]$,

2. 2.

   $\rho (F_i^1)≔F_i^2\ominus \tilde{G}(N-(2i+1)\cdot \mathrm{\Delta })$ for every $i\in [0..\lambda -1]$,

3. 3.

   $\rho (F_i^2)≔G(N-(2i+1)\cdot \mathrm{\Delta })\ominus F_i^3$ for every $i\in [0..\lambda -1]$,

4. 4.

   $\rho (F_i^3)≔\tilde{G}(N-(2i+2)\cdot \mathrm{\Delta })\ominus F_{i+1}^0$ for every $i\in [0..\lambda -2]$.

Finally, $F_{\lambda -1}^3$ expands to a string of size $N-4\lambda \mathrm{\Delta }\times N-4\lambda \mathrm{\Delta }$ filled with $0$s (notice that $N-4\lambda \mathrm{\Delta }\ge N-4\lambda {\mathrm{\Delta }}^{\prime }=N/2$). The starting nonterminal of $𝒢$ is $F_0^0$, which expands to the string $S$. In words, the nonterminals alternate between expanding to a $C_{N^{\prime },\mathrm{\Delta }}$ gadget, and expanding to a ${\tilde{C}}_{N^{\prime },\mathrm{\Delta }}$ gadget. The width (or height, if rotated) of the gadgets is always $\mathrm{\Delta }$, and the height $N^{\prime }$ (if rotated, width) decreases to fit the remaining height/width of $S$.

It follows from Lemma 14 that all $G$ and $\tilde{G}$ nonterminals used in the construction defined above can be created using $𝒪(\log N+\log \mathrm{\Delta }+\lambda )=𝒪(\log N)$ nonterminals. Clearly, the all-$0$s string of $F_{\lambda -1}^3$ can also be produced using $𝒪(\log N)$ nonterminals. The total number of nonterminals in the grammar is therefore $n=𝒪(\log N)$. For every $i\in [0..\lambda -1]$, we call the string produced by $F_i^0$ the $i$-th layer of $S$, denoted by $L_i$. In terms of indices in $S$, the $i$-th layer of $S$ is defined as $L_i=S(i\mathrm{\Delta }..N-i\mathrm{\Delta }](i\mathrm{\Delta }..N-i\mathrm{\Delta }]$. The $\mathrm{\Delta }$ right columns of $L_i$ are an occurrence of $C_{N^{\prime },\mathrm{\Delta }}$ with $N^{\prime }=N-2i\mathrm{\Delta }$ being the height of $L_i$.

We proceed to prove that no grammar ${𝒢}^{\prime }$ with $o(N/{\log }^{2}N)$ nonterminals and depth less than $c\log N$ can derive $S$. Assume to the contrary that such a grammar ${𝒢}^{\prime }=({𝒱}^{\prime },{𝒮}^{\prime },{\rho }^{\prime })$ exists. For any nonterminal $X\in {𝒱}^{\prime }$ and $i\in [\lambda ]$, we say that the nonterminal $X$ contains $L_i$ if it expands to $S[x..x^{\prime }][y..y^{\prime }]$ such that $(i\mathrm{\Delta }..N-i\mathrm{\Delta }]\subseteq [x..x^{\prime }]\cap [y..y^{\prime }]$, i.e., ${\mathrm{Exp}}_{{𝒢}^{\prime }}(X)$ is a superstring of $L_i$. Let $P=V_1,V_2,\mathrm{\dots }{V}_d$ be the sequence of nonterminals obtained by traversing the derivation tree ${𝒯}_{𝒢}$ from the root to the leaf corresponding to position $(N/2,N/2)$. Notice that position $(N/2,N/2)$ is contained in all $\lambda$ layers of $S$. For every $i\in [\lambda /2]$, let $X_i$ be the last nonterminal in $P$ whose expansion contains $L_{2i}$. Since $V_1$ expands to $S$, which contains all layers of $S$, all $X_i$’s are well defined. We show that for every $i\in [\lambda /2-1]$, $X_i$ strictly precedes $X_{i+1}$ in $P$, which implies that $|P|\ge \lambda /2=c\log N$, contradicting .

Since $L_{2i}$ contains $L_{2(i+1)}$ as a substring, it is clear that $X_i$ weakly precedes $X_{i+1}$ in $P$. Assume to the contrary that $X_i$ does not strictly precede $X_{i+1}$, which implies $X_i=X_{i+1}$. Let $X^{\prime }=X_i=X_{i+1}$, and let the production rule of $X^{\prime }$ be ${\rho }^{\prime }(X^{\prime })=B^{\prime }\ominus C^{\prime }$. Assume that the production rule of $X^{\prime }$ is a vertical concatenation rule, as the other case (horizontal concatenation rule) is symmetric. Note that it is impossible for the production rule of $X^{\prime }$ to be ${\rho }^{\prime }(X^{\prime })=\sigma$ for some terminal $\sigma$, as ${\mathrm{Exp}}_{{𝒢}^{\prime }}(X^{\prime })$ contains $L_{2i}$.

We will show that the bottom row of $B^{\prime }$ contains a row of $L_{2i}$ that is not-too-close to the margins of $L_{2i}$ (See Figure 5). Specifically, we will show that the bottom row of $B^{\prime }$ contains the $\tilde{z}$-th row of $L_{2i}$ with $\tilde{z}$ being at distance at least $2\mathrm{\Delta }$ from the top and the bottom of $L_{2i}$.

Let the string ${\mathrm{Exp}}_{{𝒢}^{\prime }}(X^{\prime })$ be $S_{X^{\prime }}=S[x..x^{\prime }][y..y^{\prime }]$. Since $S_{X^{\prime }}$ contains $L_{2i}$, it holds that $(2i\mathrm{\Delta }..N-2i\mathrm{\Delta }]\subseteq [x..x^{\prime }]\cap [y..y^{\prime }]$. We claim that both $B^{\prime }$ and $C^{\prime }$ do not contain $L_{2i+2}$. If $X^{\prime }=V_{\mathrm{\ell }}$ and $V_{\mathrm{\ell }+1}=B^{\prime }$, we have that $B^{\prime }$ does not contain $L_{2i+2}$ by the maximality of $V_{\mathrm{\ell }}$ in the sequence $P$. Recall that the position $(N/2,N/2)$ is contained in $B^{\prime }$ (and not in $C^{\prime }$). This implies that ${\mathrm{Exp}}_{{𝒢}^{\prime }}(C^{\prime })$ does not contain the unique square of $0$s with dimensions $N-2\lambda \mathrm{\Delta }\times N-2\lambda \mathrm{\Delta }$ at the center of $S$, which is a necessary condition for containing any layer of $S$. Symmetric arguments can be made if $V_{\mathrm{\ell }+1}=C^{\prime }$.

Intuitively, the fact that both $B^{\prime }$ and $C^{\prime }$ do not contain $L_{2i+2}$ means that the production rule ${\rho }^{\prime }(X^{\prime })=B^{\prime }\ominus C^{\prime }$ “cuts” the occurrence of $L_{2i+2}$ within $S_{X^{\prime }}$. Formally, let $S_{B^{\prime }}$ denote ${\mathrm{Exp}}_{{𝒢}^{\prime }}(B^{\prime })$. It holds that $S_{B^{\prime }}=S[x..z][y..y^{\prime }]$ for some $z\in ((2i+2)\mathrm{\Delta }..N-(2i+2)\mathrm{\Delta }]$. Consider the bottom row of $S_{B^{\prime }}$ i.e. $S[z][y..y^{\prime }]$. Since the interval $[y..y^{\prime }]$ contains the horizontal span of $L_{2i}$, the bottom row $S[z][y..y^{\prime }]$ of $B^{\prime }$ contains the $\tilde{z}$-th row of $L_{2i}$, with $\tilde{z}=z-2i\mathrm{\Delta }$. Indeed, we have $\tilde{z}\in (2\mathrm{\Delta }..N-(4i+2)\mathrm{\Delta }]$, and in particular $\tilde{z}\in (2\mathrm{\Delta }..h-2\mathrm{\Delta }]$ with $h=N-4i\mathrm{\Delta }$ being the height of $L_{2i}$. It follows that $S[z][y..y^{\prime }]$ contains the $\tilde{z}$-th row of $C=C_{N-4i\mathrm{\Delta },\mathrm{\Delta }}$, which constitutes the rightmost $\mathrm{\Delta }$ columns of $L_{2i}$.

Let us focus on $R$, the $\tilde{z}$-th row of $C$ (See Figure 6). Recall that we took the largest $M^{\prime }=2^n$ such that $M^{\prime }(\log M^{\prime }+2)\le \mathrm{\Delta }/2$. Due to the maximality of $M^{\prime }$, we have $2M^{\prime }(\log 2M^{\prime }+2)>\mathrm{\Delta }/2$ which implies $M^{\prime }\in \mathrm{\Omega }(\frac{\mathrm{\Delta }}{\log N})=\mathrm{\Omega }(\frac{N}{{\log }^{2}N})$. Recall that $C$ is composed of two vertical blocks, each block consists of a vertical concatenation of ${\mathrm{𝖲𝗁𝗂𝖿𝗍𝖡𝗂𝗇}}_{M^{\prime }}$ gadgets with dimensions $2M^{\prime }\times M^{\prime }(\log M^{\prime }+2)$. In the first block, every row except possibly the last $2M^{\prime }-1$ rows is a row of some ${\mathrm{𝖲𝗁𝗂𝖿𝗍𝖡𝗂𝗇}}_{M^{\prime }}$ gadget. In the second block, every row except the first $M^{\prime }$ rows and the last $2M^{\prime }-1$ rows is a row of some ${\mathrm{𝖲𝗁𝗂𝖿𝗍𝖡𝗂𝗇}}_{M^{\prime }}$ gadget. We have $2M^{\prime }\le M^{\prime }\log M^{\prime }\le \mathrm{\Delta }/2\le 2\mathrm{\Delta }$ (the first inequality assumes $M^{\prime }\ge 4$, which occurs for a sufficiently large $N$). It follows that $[2\mathrm{\Delta }..h-2\mathrm{\Delta }]\subseteq [2M^{\prime }..h-2M^{\prime }]$ and therefore $\tilde{z}\in [2M^{\prime }..h-2M^{\prime }]$.

We have shown that $R$ contains a row of ${\mathrm{𝖲𝗁𝗂𝖿𝗍𝖡𝗂𝗇}}_{M^{\prime }}$ in both blocks of $C$. Assume that $R$ contains the $r$-th row of a ${\mathrm{𝖲𝗁𝗂𝖿𝗍𝖡𝗂𝗇}}_{M^{\prime }}$ in the left block of $C$. Due to the right block being vertically shifted by $M^{\prime }$ compared to the left block, the row of ${\mathrm{𝖲𝗁𝗂𝖿𝗍𝖡𝗂𝗇}}_{M^{\prime }}$ contained in $R$ from the second block of $C$ is $r^{\prime }=r+M^{\prime }mod2M^{\prime }$. One can verify that one of $r,r^{\prime }$ must be in $[M^{\prime }/2..3M^{\prime }/2]$, assume without loss of generality that $r\in [M^{\prime }/2..3M^{\prime }/2]$. According to Lemma 11 there is a 1D grammar deriving $R$ with $n^{\prime }$ nonterminals such that $n^{\prime }$ is the number of nonterminals in ${𝒢}^{\prime }$. Since $R$ is a superstring of the $r$-th row of ${\mathrm{𝖲𝗁𝗂𝖿𝗍𝖡𝗂𝗇}}_{M^{\prime }}$, Lemma 10 yields $n^{\prime }\ge \min \{r,2M^{\prime }-r\}\ge M^{\prime }/2\in \mathrm{\Omega }(\frac{N}{{\log }^{2}N})$, a contradiction to $n^{\prime }\in o(\frac{N}{{\log }^{2}N})$. $\mathrm{⊲}$