Proof. For all \(i \in [1 \mathinner{.\,.}n]\), it holds \(|\mathrm{RowOnes}_{A,i}| \leq n\) and \(|\mathrm{RowOnes}_{B,i}| \leq n\). Since \(T_{A,B,i}\) is a concatenation of at most \(n\) strings each of which has length at most \(n\), we thus have \(|T_{A,B,i}| \leq n^2\) for all \(i \in [1 \mathinner{.\,.}n]\). Consequently, \(|T_{A,B}| \leq n^3\). ◻

Proof. ([lm:sym-occ-and-mat-mul-equivalence-it-1]) \(\Rightarrow\) ([lm:sym-occ-and-mat-mul-equivalence-it-2]) Assume that symbol \(j\) occurs in the string \(T_{A,B,i}\). Denote \(R = \mathrm{RowOnes}_{A,i}\) and \(k = |R|\). By 9, the assumption that \(j\) occurs in \(T_{A,B,i}\) implies that there exists \(t \in [1 \mathinner{.\,.}k]\) such that \(j\) occurs in the string \(\mathrm{RowOnes}_{B,R[t]}\). By definition of \(\mathrm{RowOnes}_{B,R[t]}\), this implies that \(B[R[t],j] = {\tt 1}\). On the other hand, by definition of \(R = \mathrm{RowOnes}_{A,i}\), we have \(A[i,R[t]] = {\tt 1}\). Consequently, \(A[i,R[t]] \wedge B[R[t],j] = {\tt 1}\). Hence, \((AB)[i,j] = {\tt 1}\).

([lm:sym-occ-and-mat-mul-equivalence-it-2]) \(\Rightarrow\) ([lm:sym-occ-and-mat-mul-equivalence-it-1]) Let us now assume that \((AB)[i,j] = {\tt 1}\). This implies that there exists \(p \in [1 \mathinner{.\,.}n]\) such that \(A[i,p] = {\tt 1}\) and \(B[p,j] = {\tt 1}\). Denote again \(R = \mathrm{RowOnes}_{A,i}\) and \(k = |R|\). On the one hand, \(A[i,p] = {\tt 1}\) implies that \(p\) occurs in \(R\), i.e., there exists \(t \in [1 \mathinner{.\,.}k]\) such that \(p = R[t]\). On the other hand, by \(B[p,j] = {\tt 1}\), we obtain that \(j\) occurs in \(\mathrm{RowOnes}_{B,p} = \mathrm{RowOnes}_{B,R[t]}\). We have thus proved that there exists \(t \in [1 \mathinner{.\,.}k]\) such that \(j\) occurs in \(\mathrm{RowOnes}_{B,R[t]}\). Since \(\mathrm{RowOnes}_{B,R[t]}\) is a substring of \(T_{A,B,i}\), we thus obtain that \(j\) occurs in \(T_{A,B,i}\). ◻

Proof. Let \(V = \{X_1, \dots, X_n, Y_1, \dots, Y_n, S\}\). For every \(i \in [1 \mathinner{.\,.}n]\), we set \(\mathrm{rhs}_{G}(X_i) = \mathrm{RowOnes}_{B,i} \in \{1, \dots, n\}^{*}\) (8). For every \(i \in [1 \mathinner{.\,.}n]\), letting \(R = \mathrm{RowOnes}_{A,i}\) and \(k = |R|\), we set \(\mathrm{rhs}_{G}(Y_i) = X_{R[1]} \cdot X_{R[2]} \cdots X_{R[k]}\), with the right-hand side interpreted as \(\varepsilon\) if \(k=0\). Finally, we set \(\mathrm{rhs}_{G}(S) = Y_1 \cdot Y_2 \cdots Y_n\).

To construct \(G\), we proceed as follows:

1. First, in \(\mathcal{O}(n^2)\) time we compute the strings \(\mathrm{RowOnes}_{A,i}\) and \(\mathrm{RowOnes}_{B,i}\) for all \(i \in [1 \mathinner{.\,.}n]\).

2. Given the above strings, the construction of \(\mathrm{rhs}_{G}(N)\) for all \(N \in V\) takes \(\mathcal{O}(n^2)\) time.

In total, the construction takes \(\mathcal{O}(n^2)\) time.

To show that \(L(G) = \{T_{A,B}\}\), it suffices to observe that, for every \(i \in [1 \mathinner{.\,.}n]\), it holds \(\mathrm{exp}_{G}(Y_i) = T_{A,B,i}\) (see 9). Thus, \(L(G) = \{\mathrm{exp}_{G}(S)\} = \{\bigodot_{i=1,\dots,n}\mathrm{exp}_{G}(Y_i)\} = \{T_{A,B}\}\). ◻

Proof. Let \(A,B \in \{{\tt 0},{\tt 1}\}^{n \times n}\) be two given Boolean matrices. The algorithm to compute the Boolean matrix product \(AB\) proceeds as follows:

1. In this step, we compute an array \(A_{\rm sum}[0 \mathinner{.\,.}n]\) defined such that \(A_{\rm sum}[0] = 0\) and, for every \(i \in [1 \mathinner{.\,.}n]\), \(A_{\rm sum}[i] = \sum_{j=1}^{i} |T_{A,B,j}|\) (see 9). We begin by computing an array \(A_{\rm len}[1 \mathinner{.\,.}n]\) defined by \(A_{\rm len}[i] = |T_{A,B,i}|\). To this end, we first in \(\mathcal{O}(n^2)\) time compute the strings \(\mathrm{RowOnes}_{A,i}\) and \(\mathrm{RowOnes}_{B,i}\) (see 8) for all \(i \in [1 \mathinner{.\,.}n]\). Using these strings, we can then compute \(|T_{A,B,i}|\) for any \(i \in [1 \mathinner{.\,.}n]\) in \(\mathcal{O}(n)\) time (see 9). In total, computing \(A_{\rm len}[1 \mathinner{.\,.}n]\) takes \(\mathcal{O}(n^2)\) time. Using \(A_{\rm len}\), we then easily obtain \(A_{\rm sum}\) in \(\mathcal{O}(n)\) time. In total, construction of \(A_{\rm sum}[0 \mathinner{.\,.}n]\) takes \(\mathcal{O}(n^2)\) time. Observe that by 9, for any \(i \in [1 \mathinner{.\,.}n]\), it holds \[T_{A,B}(A_{\rm sum}[i-1] \mathinner{.\,.}A_{\rm sum}[i]] = T_{A,B,i}.\] If \(A_{\rm sum}[n] = 0\), then \(T_{A,B,i}\) is empty for every \(i \in [1 \mathinner{.\,.}n]\). By 2, the output matrix \(AB\) then consists only of zeros. In this case, we return the \(n \times n\) zero matrix in \(\mathcal{O}(n^2)\) time and conclude the algorithm. Henceforth, assume that \(A_{\rm sum}[n] > 0\).

2. Using 9, in \(\mathcal{O}(n^2)\) time we construct an SLG \(G = (V, \Sigma, R, S)\) such that \(\Sigma = \{1, \dots, \sigma\}\) (where \(\sigma = n\)) and \(L(G) = \{T\}\), where \(T = T_{A,B}\) (9). Note that the upper bound on the runtime of 9 implies that \(|G| = \mathcal{O}(n^2)\). Denote \(N = |T|\) and recall that \(N \leq n^3\) (8). Observe also that we then have \(\sigma = n = \Omega(N^{1/3})\).

3. In this step, we compute the product \(AB\). By 2, computing \((AB)[i,j]\) for any given \(i,j \in [1 \mathinner{.\,.}n]\) can be done using a single symbol occurrence query. More precisely, by 2 and the above discussion, it holds (see 1) \[\begin{align} (AB)[i,j] &= \mathrm{occurs}_{T_{A,B,i}}(0,|T_{A,B,i}|,j)\\ &= \mathrm{occurs}_{T_{A,B}}(A_{\rm sum}[i-1],A_{\rm sum}[i],j)\\ &= \mathrm{occurs}_{T}(A_{\rm sum}[i-1],A_{\rm sum}[i],j). \end{align}\] Using the array \(A_{\rm sum}\), in \(\mathcal{O}(n^2)\) time we prepare the arguments for a batch of \(m = n^2\) symbol occurrence queries on \(T\). Using the algorithm from the claim, we then answer all the queries (and hence compute the product \(AB\)) in \(\mathcal{O}((|G| + m) \log^{\mathcal{O}(1)} N) = \mathcal{O}(n^2 \log^{\mathcal{O}(1)} (n^3)) = \mathcal{O}(n^2 \log^{\mathcal{O}(1)} n)\) time.

In total, the algorithm takes \(\mathcal{O}(n^2 \log^{\mathcal{O}(1)} n)\) time. ◻

Proof. For each \(i \in [1 \mathinner{.\,.}m]\), let \(X_i := \text{\normalfont \texttt{\$}}_i \cdot S_i\). We first prove by induction on \(i\) that, for every \(i \in [1 \mathinner{.\,.}m]\), the first \(i+a_i\) phrases in the LZ78 factorization of \(T\) are exactly the phrases \(X_1[1], X_1[1 \mathinner{.\,.}2], \ldots, X_1[1 \mathinner{.\,.}|X_1|], \ldots, X_i[1], X_i[1 \mathinner{.\,.}2], \ldots, X_i[1 \mathinner{.\,.}|X_i|]\), i.e., \(\text{\normalfont \texttt{\$}}_1, \text{\normalfont \texttt{\$}}_1S_1[1], \ldots, \text{\normalfont \texttt{\$}}_1S_1, \ldots, \text{\normalfont \texttt{\$}}_i, \text{\normalfont \texttt{\$}}_iS_i[1], \ldots, \text{\normalfont \texttt{\$}}_iS_i\).

• For the base case \(i=1\), note that the prefix of \(T\) corresponding to \(\mathrm{prefixes}(X_1)\) is exactly \(X_1[1] \cdot X_1[1 \mathinner{.\,.}2] \cdots X_1[1 \mathinner{.\,.}|X_1|]\). The first phrase is therefore \(X_1[1]=\text{\normalfont \texttt{\$}}_1\), since \(\text{\normalfont \texttt{\$}}_1\) has not occurred earlier. After this, the unread suffix again starts with \(\text{\normalfont \texttt{\$}}_1\). More generally, whenever the phrases \(X_1[1], X_1[1 \mathinner{.\,.} 2], \ldots, X_1[1 \mathinner{.\,.}r]\) have already been produced, the next unread position starts with \(X_1[1 \mathinner{.\,.}r+1]\); this string is obtained by extending the earlier phrase \(X_1[1 \mathinner{.\,.}r]\) by one symbol, and no longer phrase can be chosen, because among all earlier phrases the only ones starting with \(\text{\normalfont \texttt{\$}}_1\) are precisely \(X_1[1], X_1[1 \mathinner{.\,.}2], \ldots, X_1[1 \mathinner{.\,.}r]\). Hence the phrases contributed by \(\mathrm{prefixes}(X_1)\) are exactly \(X_1[1], X_1[1 \mathinner{.\,.} 2], \ldots, X_1[1 \mathinner{.\,.}|X_1|]\).

• For the induction step, assume that the claim holds for some \(i \in [1 \mathinner{.\,.}m)\), and let \(\delta := i+a_i\). Then the first \(\delta\) phrases are exactly those coming from \(\mathrm{prefixes}(X_1), \ldots, \mathrm{prefixes}(X_i)\). The next unread part of \(T\) begins with \(\mathrm{prefixes}(X_{i+1})\), namely with \(X_{i+1}[1] \cdot X_{i+1}[1 \mathinner{.\,.}2] \cdots X_{i+1}[1 \mathinner{.\,.} |X_{i+1}|]\). Since \(\text{\normalfont \texttt{\$}}_{i+1}\) does not occur in the already parsed prefix, the next phrase is \(X_{i+1}[1]=\text{\normalfont \texttt{\$}}_{i+1}\). Repeating the same argument as in the base case, after the phrases \(X_{i+1}[1], X_{i+1}[1 \mathinner{.\,.} 2], \ldots, X_{i+1}[1 \mathinner{.\,.}r]\) have been produced, the next unread suffix starts with \(X_{i+1}[1 \mathinner{.\,.}r+1]\); this is obtained by extending the previous phrase \(X_{i+1}[1 \mathinner{.\,.}r]\), and it is maximal because the only earlier phrases starting with \(\text{\normalfont \texttt{\$}}_{i+1}\) are the prefixes already created in this block. Thus the phrases contributed by \(\mathrm{prefixes}(X_{i+1})\) are exactly \(X_{i+1}[1], X_{i+1}[1 \mathinner{.\,.}2], \ldots, X_{i+1}[1 \mathinner{.\,.} |X_{i+1}|]\). This proves the induction claim.

Let \(\Delta := m+a_m\). By the above, the first \(\Delta\) phrases in the LZ78 factorization of \(T\) are exactly \(\text{\normalfont \texttt{\$}}_1, \text{\normalfont \texttt{\$}}_1S_1[1], \ldots, \text{\normalfont \texttt{\$}}_1S_1, \ldots, \text{\normalfont \texttt{\$}}_m, \text{\normalfont \texttt{\$}}_mS_m[1], \ldots, \text{\normalfont \texttt{\$}}_mS_m\), and the remaining suffix is \(\bigodot_{i=1,\ldots,k} T_i\). Consider any substring of this suffix of the form \(\text{\normalfont \texttt{\$}}_t \cdot S_t \cdot \text{\normalfont \texttt{\#}}_r\), where \(t \in [1 \mathinner{.\,.}m]\) and \(r \in [1 \mathinner{.\,.} k]\). Since \(\text{\normalfont \texttt{\$}}_tS_t\) is already one of the first \(\Delta\) phrases, the string \(\text{\normalfont \texttt{\$}}_tS_t\text{\normalfont \texttt{\#}}_r\) can be chosen as the next LZ78 phrase. It is also maximal: indeed, if a longer phrase were to start here, then there would exist an earlier phrase \(Q\) that matches a longer prefix of the unread suffix and has \(\text{\normalfont \texttt{\$}}_tS_t\text{\normalfont \texttt{\#}}_r\) as a prefix. Since every nonempty LZ78 phrase is obtained from an earlier phrase by appending one symbol, repeatedly following source phrases from \(Q\) shows that every nonempty prefix of \(Q\) is also an earlier phrase. In particular, the string \(\text{\normalfont \texttt{\$}}_tS_t\text{\normalfont \texttt{\#}}_r\) itself would have to occur earlier as a phrase. This is impossible, because \(\text{\normalfont \texttt{\#}}_r\) does not occur in the prefix \(\bigodot_{i=1,\ldots,m} \mathrm{prefixes}(\text{\normalfont \texttt{\$}}_iS_i)\), and within the suffix \(\bigodot_{i=1,\ldots,k} T_i\) each substring \(\text{\normalfont \texttt{\$}}_tS_t\text{\normalfont \texttt{\#}}_r\) appears at most once: any occurrence of \(\text{\normalfont \texttt{\$}}_tS_t\text{\normalfont \texttt{\#}}_r\) must start at an occurrence of \(\text{\normalfont \texttt{\$}}_t\), and since each \(S_u\) belongs to \(\Sigma^*\) while all symbols \(\text{\normalfont \texttt{\$}}_1,\ldots,\text{\normalfont \texttt{\$}}_m,\text{\normalfont \texttt{\#}}_1,\ldots,\text{\normalfont \texttt{\#}}_k\) lie outside \(\Sigma\), the symbol \(\text{\normalfont \texttt{\$}}_t\) can occur in the suffix only as the first symbol of one of the blocks \(\text{\normalfont \texttt{\$}}_{p_{u,v}}S_{p_{u,v}}\text{\normalfont \texttt{\#}}_u\); for fixed \(r\) this follows from the strict inequalities \(p_{r,1} < \cdots < p_{r,n_r}\), and for different values of \(r\) the last symbol differs since \(\text{\normalfont \texttt{\#}}_1,\ldots,\text{\normalfont \texttt{\#}}_k\) are distinct. Therefore each substring \(\text{\normalfont \texttt{\$}}_{p_{i,j}} S_{p_{i,j}} \text{\normalfont \texttt{\#}}_i\) forms one phrase of the LZ78 factorization of \(T\), in the stated order. This proves the claimed formula for the factorization. In particular, the number of phrases is \(\Delta + \sum_{i=1}^{k} n_i = m + \sum_{j=1}^{m} |S_j| + \sum_{i=1}^{k} n_i\).

It remains to verify the formulas for the LZ78 representation.

• A phrase \(\text{\normalfont \texttt{\$}}_i\), where \(i \in [1 \mathinner{.\,.}m]\), is encoded as \((0,\text{\normalfont \texttt{\$}}_i)\) by definition.

• Next, let us consider a phrase \(\text{\normalfont \texttt{\$}}_i \cdot S_i[1 \mathinner{.\,.}j]\), where \(i \in [1 \mathinner{.\,.}m]\) and \(j \in [1 \mathinner{.\,.}|S_i|]\). This is the phrase \(X_i[1 \mathinner{.\,.}j+1]\), and it is the \((a_{i-1}+(i-1)+(j+1))\)th phrase in the factorization. Its source phrase is the immediately preceding phrase \(X_i[1 \mathinner{.\,.}j]\), whose index is \(a_{i-1}+(i-1)+j\). Therefore its encoding is \((a_{i-1}+(i-1)+j, S_i[j])\).

• Finally, let us consider a phrase \(\text{\normalfont \texttt{\$}}_{p_{i,j}} \cdot S_{p_{i,j}} \cdot \text{\normalfont \texttt{\#}}_i\), where \(i \in [1 \mathinner{.\,.}k]\) and \(j \in [1 \mathinner{.\,.}n_i]\). Its source is the phrase \(\text{\normalfont \texttt{\$}}_{p_{i,j}} \cdot S_{p_{i,j}}\), and by the first part of the proof that source is the \((a_{p_{i,j}} + p_{i,j})\)th phrase. Hence the encoding of \(\text{\normalfont \texttt{\$}}_{p_{i,j}} \cdot S_{p_{i,j}} \cdot \text{\normalfont \texttt{\#}}_i\) is \((a_{p_{i,j}} + p_{i,j}, \text{\normalfont \texttt{\#}}_i)\).

 ◻

Proof. For all \(i \in [1 \mathinner{.\,.}n]\), it holds \(|\mathrm{RowOnes}_{A,i}| \leq n\) and \(|\mathrm{RowOnes}_{B,i}| \leq n\). Thus, \(X_{A,B,i}\) is a concatenation of at most \(n\) strings each of which has length at most \(n+2\), and hence \(|X_{A,B,i}| \leq n(n+2)\) for all \(i \in [1 \mathinner{.\,.}n]\). On the other hand, by 10, for every \(i \in [1 \mathinner{.\,.}n]\), letting \(k = |\mathrm{RowOnes}_{B,i}|\), it holds \(|\mathrm{prefixes}((n+i) \cdot \mathrm{RowOnes}_{B,i})| = (k+1)(k+2)/2 \leq (n+1)(n+2)/2\). Consequently, \(|X_{A,B}| \leq n(n+1)(n+2)/2 + n^2(n+2) = \tfrac{3}{2}n^3 + \tfrac{7}{2}n^2 + n \leq 6n^3\). ◻

Proof. Observe that letting \(S_i = \mathrm{RowOnes}_{B,i}\), \(n_i = |\mathrm{RowOnes}_{A,i}|\), and \((p_{i,j})_{j=1,\ldots,n_i}\) (where \(i \in [1 \mathinner{.\,.}n]\)) be the sequence of symbols in \(\mathrm{RowOnes}_{A,i}\), the string \(T\) from 3 is equal to the string \(X_{A,B}\), assuming we map symbols in the sets \(\{\text{\normalfont \texttt{\$}}_1, \dots, \text{\normalfont \texttt{\$}}_n\}\) and \(\{\text{\normalfont \texttt{\#}}_1, \dots, \text{\normalfont \texttt{\#}}_n\}\) so that for every \(i \in [1 \mathinner{.\,.}n]\), \(\text{\normalfont \texttt{\$}}_i\) (resp. \(\text{\normalfont \texttt{\#}}_i\)) is mapped to \(n + i\) (resp.\(2n + i\)). By 3, we can thus compute the LZ78 representation of \(X_{A,B}\) as follows:

1. In \(\mathcal{O}(n^2)\) time, we compute, for \(i \in [1 \mathinner{.\,.}n]\), the strings \(A_i = \mathrm{RowOnes}_{A,i}\) and \(B_i = \mathrm{RowOnes}_{B,i}\).

2. In \(\mathcal{O}(n)\) time, we compute an array \({\rm sum}[0 \mathinner{.\,.}n]\) defined such that \({\rm sum}[0] = 0\) and, for every \(i \in [1 \mathinner{.\,.}n]\), \({\rm sum}[i] = {\rm sum}[i-1] + |B_i|\).

3. For \(i=1,\ldots,n\), perform the following steps:

   1. First, append the pair \((0, n+i)\) to the output LZ78 representation.

   2. For \(j=1,\ldots,|B_i|\), append the pair \(({\rm sum}[i-1]+(i-1)+j,B_i[j])\) to the output LZ78 representation.

   In total, this takes \(\mathcal{O}(n^2)\) time.

4. For \(i=1,\ldots,n\), scan the sequence \(A_i\) left-to-right and, for every \(j \in [1 \mathinner{.\,.}|A_i|]\), append the pair \(({\rm sum}[A_i[j]] + A_i[j], 2n + i)\) to the output LZ78 representation. In total, this takes \(\mathcal{O}(n^2)\) time.

In total, the computation takes \(\mathcal{O}(n^2)\) time. An equivalent optimized implementation, which avoids explicitly storing the strings \(A_i\) and \(B_i\), is given in 3. ◻

Proof. Let \(A,B \in \{{\tt 0},{\tt 1}\}^{n \times n}\) be two given Boolean matrices. The algorithm to compute the Boolean matrix product \(AB\) proceeds as follows:

1. In the first step, we compute the integer \(\Delta = \sum_{i=1}^{n} |\mathrm{prefixes}((n+i) \cdot \mathrm{RowOnes}_{B,i})|\). To this end, we first in \(\mathcal{O}(n^2)\) time compute the strings \(\mathrm{RowOnes}_{B,i}\) for all \(i \in [1 \mathinner{.\,.}n]\). Using their lengths, the computation of \(\Delta\) takes \(\mathcal{O}(n)\) time (see 10).

2. In the second step, we compute an array \(A_{\rm sum}[0 \mathinner{.\,.}n]\) defined such that \(A_{\rm sum}[0] = 0\) and, for every \(i \in [1 \mathinner{.\,.}n]\), \(A_{\rm sum}[i] = \sum_{j=1}^{i} |X_{A,B,j}|\) (see 11). We begin by computing an array \(A_{\rm len}[1 \mathinner{.\,.}n]\) defined by \(A_{\rm len}[i] = |X_{A,B,i}|\). To this end, we first in \(\mathcal{O}(n^2)\) time compute the strings \(\mathrm{RowOnes}_{A,i}\) and \(\mathrm{RowOnes}_{B,i}\) (see 8) for all \(i \in [1 \mathinner{.\,.}n]\). Using these strings, we can then compute \(|X_{A,B,i}|\) for any \(i \in [1 \mathinner{.\,.}n]\) in \(\mathcal{O}(n)\) time (see 11). In total, computing \(A_{\rm len}[1 \mathinner{.\,.}n]\) takes \(\mathcal{O}(n^2)\) time. Using \(A_{\rm len}\), we then easily obtain \(A_{\rm sum}\) in \(\mathcal{O}(n)\) time. In total, construction of \(A_{\rm sum}[0 \mathinner{.\,.}n]\) takes \(\mathcal{O}(n^2)\) time. Observe that by 11, for any \(i \in [1 \mathinner{.\,.}n]\), it holds \[X_{A,B}(\Delta + A_{\rm sum}[i-1] \mathinner{.\,.}\Delta + A_{\rm sum}[i]] = X_{A,B,i}.\]

3. Using 11, in \(\mathcal{O}(n^2)\) time we compute the LZ78 representation of the string \(T = X_{A,B}\) (11). Note that \(T\) is over alphabet \(\Sigma = \{1, \dots, \sigma\}\), where \(\sigma = 3n\). Note also that by 11 and 3, it follows that \(z_{78}(T) = n + \sum_{i=1}^{n} |\mathrm{RowOnes}_{B,i}| + \sum_{i=1}^{n} |\mathrm{RowOnes}_{A,i}| \leq n + 2n^2\). Denote \(N = |T|\) and recall that \(N \leq 6n^3\) (10). We then have \(\sigma = 3n = \Omega(N^{1/3})\).

4. In this step, we compute the product \(AB\). By 2, computing \((AB)[i,j]\) for any given \(i,j \in [1 \mathinner{.\,.}n]\) can be done using a single symbol occurrence query on the string \(T_{A,B,i}\) (9). More precisely, by 2, it holds \((AB)[i,j] = \mathrm{occurs}_{T_{A,B,i}}(0,|T_{A,B,i}|,j)\). On the other hand, note that by comparing 9 and 11, we immediately have that since \(j \in [1 \mathinner{.\,.}n]\), it holds \(\mathrm{occurs}_{T_{A,B,i}}(0,|T_{A,B,i}|,j) = \mathrm{occurs}_{X_{A,B,i}}(0,|X_{A,B,i}|,j)\). Putting this together, we thus obtain that \[\begin{align} (AB)[i,j] &= \mathrm{occurs}_{T_{A,B,i}}(0,|T_{A,B,i}|,j)\\ &= \mathrm{occurs}_{X_{A,B,i}}(0,|X_{A,B,i}|,j)\\ &= \mathrm{occurs}_{X_{A,B}}(\Delta+A_{\rm sum}[i-1],\Delta+A_{\rm sum}[i],j)\\ &= \mathrm{occurs}_{T}(\Delta+A_{\rm sum}[i-1],\Delta+A_{\rm sum}[i],j). \end{align}\] Using the array \(A_{\rm sum}\), in \(\mathcal{O}(n^2)\) time we prepare the arguments for a batch of \(m = n^2\) symbol occurrence queries on \(T\). Using the algorithm from the claim, we then answer all the queries (and hence compute the product \(AB\)) in \(\mathcal{O}((z_{78}(T) + m) \log^{\mathcal{O}(1)} N) = \mathcal{O}(n^2 \log^{\mathcal{O}(1)} (n^3)) = \mathcal{O}(n^2 \log^{\mathcal{O}(1)} n)\) time.

In total, the algorithm takes \(\mathcal{O}(n^2 \log^{\mathcal{O}(1)} n)\) time. ◻

Proof. If \(b \geq e\), then we have \(kb \geq ke\), \(\mathrm{occurs}_{T}(b,e,c) = 0\), and \(\mathrm{rank}_{T'}(kb,ke,c) = 0\). Thus, the claim in this case holds. Let us now assume \(b < e\). By 12, \(T'(kb \mathinner{.\,.}ke] = \bigodot_{i=b+1,\dots,e} T[i]^{k}\). Thus, if \(c\) does not occur in \(T(b \mathinner{.\,.}e]\), then it also does not occur in \(T'(kb \mathinner{.\,.}ke]\), and hence \(\mathrm{rank}_{T'}(kb,ke,c) = 0\). If \(c\) occurs in \(T(b \mathinner{.\,.}e]\) then, letting \(i \in (b \mathinner{.\,.}e]\) be such that \(T[i] = c\), \(T[i]^{k}\) occurs in \(T'(kb \mathinner{.\,.}ke]\), and hence \(\mathrm{rank}_{T'}(kb,ke,c) \geq k\). ◻

Proof. Denote \(V = \{N_1, \dots, N_g\}\) and let \(s \in [1 \mathinner{.\,.}g]\) be such that \(S = N_s\). Denote \(h = \lfloor \log k \rfloor\), and let \(p_1,\ldots,p_{h'} \in \mathbb{Z}_{\geq 0}\) be the unique nonempty increasing sequence satisfying \(k = \sum_{i=1}^{h'} 2^{p_i}\). We then let \(V' = \{X_i\}_{i \in [1 \mathinner{.\,.}g]} \cup \{Y_c\}_{c \in [1 \mathinner{.\,.}\sigma]} \cup \{Z_{c,j}\}_{c \in [1 \mathinner{.\,.}\sigma],j \in [0 \mathinner{.\,.}h]}\) and \(S' = X_{s}\), where the definitions of rules in \(V'\) are as follows:

• To define \(\mathrm{rhs}_{G'}(X_i)\), where \(i \in [1 \mathinner{.\,.}g]\), we consider two cases. If \(|\mathrm{rhs}_{G}(N_i)| = 2\), then, letting \(j_1, j_2 \in [1 \mathinner{.\,.}g]\) be such that \(\mathrm{rhs}_{G}(N_i) = N_{j_1} N_{j_2}\), we define \(\mathrm{rhs}_{G'}(X_i) = X_{j_1} X_{j_2}\). Otherwise, letting \(c \in [1 \mathinner{.\,.}\sigma]\) be such that \(\mathrm{rhs}_{G}(N_i) = c\), we let \(\mathrm{rhs}_{G'}(X_i) = Y_c\).

• For every \(c \in [1 \mathinner{.\,.}\sigma]\), we define \(\mathrm{rhs}_{G'}(Y_c) = \bigodot_{t=1,\ldots,h'} Z_{c,p_t}\).

• To define \(\mathrm{rhs}_{G'}(Z_{c,j})\), where \(c \in [1 \mathinner{.\,.}\sigma]\) and \(j \in [0 \mathinner{.\,.}h]\), we again consider two cases. If \(j = 0\), then we let \(\mathrm{rhs}_{G'}(Z_{c,j}) = c\). Otherwise, we let \(\mathrm{rhs}_{G'}(Z_{c,j}) = Z_{c,j-1} Z_{c,j-1}\).

The size of \(G'\) is \(\mathcal{O}(g + \sigma h' + \sigma h) = \mathcal{O}(|G| + \sigma \log k)\). Given \(G\), we can easily construct \(G'\) in \(\mathcal{O}(|G| + \sigma \log k)\) time.

To show that \(L(G') = \{\mathrm{stretch}_{k}(T)\}\), it suffices to observe that, for every \(c \in [1 \mathinner{.\,.}\sigma]\) and \(j \in [0 \mathinner{.\,.}h]\), it holds \(\mathrm{exp}_{G'}(Z_{c,j}) = c^{2^j}\). This implies that, for every \(c \in [1 \mathinner{.\,.}\sigma]\), \(\mathrm{exp}_{G'}(Y_c) = \mathrm{exp}_{G'}(\bigodot_{j=1,\ldots,h'} Z_{c,p_j}) = \bigodot_{j=1,\ldots,h'} \mathrm{exp}_{G'}(Z_{c,p_j}) = \bigodot_{j=1,\ldots,h'} c^{2^{p_j}} = c^{\sum_{j=1}^{h'}2^{p_j}} = c^k\). Consequently, for every \(i \in [1 \mathinner{.\,.}g]\), \(\mathrm{exp}_{G'}(X_i) = \mathrm{stretch}_{k}(\mathrm{exp}_{G}(N_i))\). In particular, \(\mathrm{exp}_{G'}(S') = \mathrm{exp}_{G'}(X_s) = \mathrm{stretch}_{k}(\mathrm{exp}_{G}(N_s)) = \mathrm{stretch}_{k}(\mathrm{exp}_{G}(S)) = \mathrm{stretch}_{k}(T)\), and hence we obtain \(L(G') = \{\mathrm{exp}_{G'}(S')\} = \{\mathrm{stretch}_{k}(T)\}\). ◻

Proof. The result follows by combining 2 and 12. ◻

Proof. Let \(A,B \in \{{\tt 0},{\tt 1}\}^{n \times n}\) be two given Boolean matrices. The algorithm to compute the Boolean matrix product \(AB\) proceeds as follows:

1. We compute an array \(A_{\rm sum}[0 \mathinner{.\,.}n]\) defined so that \(A_{\rm sum}[0] = 0\) and, for every \(i \in [1 \mathinner{.\,.}n]\), \(A_{\rm sum}[i] = \sum_{j=1}^{i} |T_{A,B,j}|\) (where \(T_{A,B,j}\) is as in 9). Using the algorithm presented in the proof of [th:hardness-of-slg-symbol-occ], the computation of \(A_{\rm sum}\) takes \(\mathcal{O}(n^2)\) time. Note that, for every \(i \in [1 \mathinner{.\,.}n]\), we then have \(T_{A,B}(A_{\rm sum}[i-1] \mathinner{.\,.}A_{\rm sum}[i]] = T_{A,B,i}\) (see 9).

2. We check if \(A_{\rm sum}[n] = 0\). If so, then by 9, it holds \(|T_{A,B}| = 0\). In this case, by 2, the output matrix \(AB\) consists only of zeros. Thus, in this case we return the \(n \times n\) matrix consisting of zeros in \(\mathcal{O}(n^2)\) time, and conclude the algorithm. Henceforth, we assume that \(A_{\rm sum}[n] > 0\), i.e., \(|T_{A,B}| > 0\).

3. Using 9, in \(\mathcal{O}(n^2)\) time we construct an SLG \(G_{A,B} = (V_{A,B}, \Sigma, R_{A,B}, S_{A,B})\) such that \(\Sigma = \{1, \dots, \sigma\}\) (where \(\sigma = n\)) and \(L(G_{A,B}) = \{T_{A,B}\}\) (9). Note that the upper bound on the runtime of 9 implies that \(|G_{A,B}| = \mathcal{O}(n^2)\). Note also that \(|T_{A,B}| \leq n^3\) (8).

4. Apply 13 to the SLG \(G_{A,B}\) with \(k = \lfloor 2^{1/\mu} \cdot n^{3(1/\mu-1)} \rfloor\) (note that we can apply 13 here, since \(T_{A,B} \neq \varepsilon\)). This takes \(\mathcal{O}(|G_{A,B}| + \sigma \log k) = \mathcal{O}(n^2)\) time, and we obtain an SLG \(G = (V, \Sigma, R, S)\) such that \(L(G) = \{T\}\), where \(T = \mathrm{stretch}_{k}(T_{A,B})\) (12). The upper bound on the runtime of 13 implies that \(|G| = \mathcal{O}(n^2)\). Denote \(N = |T|\) and note that \[N = k \cdot |T_{A,B}| \leq \lfloor 2^{1/\mu} \cdot n^{3(1/\mu-1)} \rfloor \cdot n^3 \leq 2^{1/\mu} \cdot n^{3/\mu}.\] Since \(\sigma = n\), we thus obtain \(N \leq 2^{1/\mu} \cdot \sigma^{3/\mu}\), i.e., \(\sigma = \Omega(N^{\mu/3})\). Thus, all the conditions for applying the algorithm from the claim hold for SLG \(G\).

5. In this step, we compute the product \(AB\). We first make the following observations:

   • Note that \(N^{1-\mu} \leq (2^{1/\mu} \cdot n^{3/\mu})^{1-\mu} = 2^{1/\mu-1} \cdot n^{3(1/\mu-1)}\). This implies \(\lfloor N^{1-\mu} \rfloor \leq \lfloor 2^{1/\mu-1} \cdot n^{3(1/\mu-1)} \rfloor \leq \tfrac{1}{2} \lfloor 2^{1/\mu} \cdot n^{3(1/\mu-1)} \rfloor = k/2\).

   • Consider any \(c \in \Sigma\) and any \(b,e \in [0 \mathinner{.\,.}|T_{A,B}|]\). Let \(x\) be a \(\lfloor N^{1-\mu} \rfloor\)-additive approximation of \(\mathrm{rank}_{T}(kb,ke,c)\). Observe that:

     • If \(\mathrm{occurs}_{T_{A,B}}(b,e,c) = 0\), then since \(T = \mathrm{stretch}_{k}(T_{A,B})\), it follows by 4 that \(\mathrm{rank}_{T}(kb,ke,c) = 0\). Thus, by 3, \(x < \lfloor N^{1-\mu} \rfloor \leq k/2\).

     • If \(\mathrm{occurs}_{T_{A,B}}(b,e,c) = 1\), then by 4, it holds \(\mathrm{rank}_{T}(kb,ke,c) \geq k\). Thus, by 3, we have \(x > \mathrm{rank}_{T}(kb,ke,c) - \lfloor N^{1-\mu} \rfloor \geq k/2\).

     Consequently, we can determine \(\mathrm{occurs}_{T_{A,B}}(b,e,c)\) from \(x\) in \(\mathcal{O}(1)\) time.

   By 2, for any \(i,j \in [1 \mathinner{.\,.}n]\), it holds \((AB)[i,j] = \mathrm{occurs}_{T_{A,B}}(A_{\rm sum}[i-1],A_{\rm sum}[i],j)\). Consequently, to compute the product \(AB\), we compute the \(\lfloor N^{1-\mu} \rfloor\)-additive approximation of the value \(\mathrm{rank}_{T}(k\cdot A_{\rm sum}[i-1],k\cdot A_{\rm sum}[i],j)\) for every \(i,j \in [1 \mathinner{.\,.}n]\). By the above discussion, this lets us compute all the values in \(AB\). Answering the batch of \(m = n^2\) approximate rank queries takes \(\mathcal{O}((|G| + m) \log^{\mathcal{O}(1)} N) = \mathcal{O}(n^2 \log^{\mathcal{O}(1)} (n^{3/\mu})) = \mathcal{O}(n^2 \log^{\mathcal{O}(1)} n)\) time.

In total, the algorithm takes \(\mathcal{O}(n^2 \log^{\mathcal{O}(1)} n)\) time. ◻

Proof. For every \(j \in [1 \mathinner{.\,.}d]\), it holds \(|\mathrm{OneVectors}_{A,j}| \leq n\) (13). On the other hand, for every \(i \in [1 \mathinner{.\,.}n]\), \(|\mathrm{OnePos}_{a_i}| \leq d\) (14). Consequently, for every \(i \in [1 \mathinner{.\,.}n]\), we have \(|U_{A,i}| \leq n d\) and hence we obtain that \(|U_A| \leq n^2 d\) (see 15). ◻

Proof. ([lm:reduce-ov-to-range-distinct-count-it-1]) \(\Rightarrow\) ([lm:reduce-ov-to-range-distinct-count-it-2]) Assume that \(\left\langle a_i, a_j \right\rangle \neq 0\). Then, there exists \(p \in [1 \mathinner{.\,.}d]\) such that \(a_i[p] = {\tt 1}\) and \(a_j[p] = {\tt 1}\). By 13, this implies that the symbol \(j\) occurs in the string \(\mathrm{OneVectors}_{A,p}\). On the other hand, symbol \(p\) occurs in \(\mathrm{OnePos}_{a_i}\) (14). By 15, this implies that \(\mathrm{OneVectors}_{A,p}\) is a substring of \(U_{A,i}\). Consequently, the symbol \(j\) occurs in the string \(U_{A,i}\).

([lm:reduce-ov-to-range-distinct-count-it-2]) \(\Rightarrow\) ([lm:reduce-ov-to-range-distinct-count-it-1]) Assume now that the symbol \(j\) occurs in the string \(U_{A,i}\). Denote \(R = \mathrm{OnePos}_{a_i}\) and \(k = |R|\). By 15, the assumption that \(j\) occurs in \(U_{A,i}\) implies that there exists \(t \in [1 \mathinner{.\,.}k]\) such that \(j\) occurs in \(\mathrm{OneVectors}_{A,R[t]}\). By 13, this implies that \(a_j[R[t]] = {\tt 1}\). On the other hand, by 14, we have \(a_i[R[t]] = {\tt 1}\). Thus, we obtain \(\left\langle a_i, a_j \right\rangle \neq 0\). ◻

Proof. The equivalence follows immediately by observing that by 5, for every \(i \in [1 \mathinner{.\,.}n]\), it holds \[\mathrm{distinct}_{U_{A,i}}(0, |U_{A,i}|) = |\{j \in [1 \mathinner{.\,.}n] : \left\langle a_i, a_j \right\rangle \neq 0\}|. \qedhere\] ◻

Proof. Let \(V = \{X_1, \ldots, X_d, Y_1, \ldots, Y_n, S\}\). For \(j \in [1 \mathinner{.\,.}d]\), we set \(\mathrm{rhs}_{G}(X_j) = \mathrm{OneVectors}_{A,j} \in \{1, \dots, n\}^{*}\) (13). For every \(i \in [1 \mathinner{.\,.}n]\), letting \(R = \mathrm{OnePos}_{a_i}\) (14) and \(k = |R|\), we set \(\mathrm{rhs}_{G}(Y_i) = X_{R[1]} \cdot X_{R[2]} \cdots X_{R[k]}\), with the right-hand side interpreted as \(\varepsilon\) if \(k=0\). Finally, we set \(\mathrm{rhs}_{G}(S) = Y_{1} \cdot Y_{2} \cdots Y_{n}\).

To construct \(G\), we proceed as follows:

1. In \(\mathcal{O}(dn)\) time we compute the strings \(\mathrm{OneVectors}_{A,j}\) for all \(j \in [1 \mathinner{.\,.}d]\).

2. In \(\mathcal{O}(dn)\) time we compute the strings \(\mathrm{OnePos}_{a_i}\) for all \(i \in [1 \mathinner{.\,.}n]\).

3. Given the above strings, the construction of \(\mathrm{rhs}_{G}(N)\) for all \(N \in V\) takes \(\mathcal{O}(dn)\) time.

In total, the construction takes \(\mathcal{O}(dn)\) time.

To show that \(L(G) = \{U_A\}\), it suffices to observe that, for every \(i \in [1 \mathinner{.\,.}n]\), it holds \(\mathrm{exp}_{G}(Y_i) = U_{A,i}\) (15). Thus, \(L(G) = \{\mathrm{exp}_{G}(S)\} = \{\bigodot_{i=1,\ldots,n} \mathrm{exp}_{G}(Y_i)\} = \{U_{A}\}\). ◻

Proof. Suppose that there exists a constant \(\epsilon > 0\) such that, given any SLG \(G = (V, \Sigma, R, S)\) representing a string \(T \in \Sigma^{N}\) (where \(\Sigma = \{1, \ldots, \sigma\}\) and \(\sigma = \Omega((N / \log N)^{1/2})\)), we can answer any batch of \(m = \Omega(|G| / \log N)\) range distinct counting queries in \(\mathcal{O}(m|G|^{1-\epsilon} \log^{c'} N)\) time, where \(c' > 0\) is some constant. We will show that this implies that 7 does not hold.

Denote \(\epsilon' = \epsilon/2\). Consider any sequence \(A = (a_1, \ldots, a_n)\) of \(n \geq 1\) binary vectors of dimension \(d = c\log n\), where \(c \geq 1\) is a constant. Given the sequence \(A\), we determine whether there exist \(i,j \in [1 \mathinner{.\,.}n]\) such that \(\left\langle a_i, a_j \right\rangle = 0\) as follows:

1. In \(\mathcal{O}(dn)\) time we check if there exists \(i \in [1 \mathinner{.\,.}n]\) such that \(a_i = {\tt 0}^{d}\). If we find such \(i\), we immediately return that the given OV instance has a pair \(i,j \in [1 \mathinner{.\,.}n]\) satisfying \(\left\langle a_i, a_j \right\rangle = 0\), and the algorithm is complete. Let us now assume that no such \(i\) was found. Denote \(p = \sum_{i=1}^{n} \sum_{j=1}^{d} a_i[j]\). Since \(A\) does not contain the zero vector, we have \(p \geq n\). Note that by 15, we then obtain \(|U_{A}| \geq p \geq n\).

2. Next, we compute an array \(A_{\rm sum}[0 \mathinner{.\,.}n]\) defined such that \(A_{\rm sum}[0] = 0\) and, for every \(i \in [1 \mathinner{.\,.}n]\), \(A_{\rm sum}[i] = \sum_{j=1}^{i} |U_{A,j}|\) (see 15). We first compute an array \(A_{\rm len}[1 \mathinner{.\,.}n]\) defined by \(A_{\rm len}[i] = |U_{A,i}|\). To this end, we first in \(\mathcal{O}(dn)\) time compute the strings \(\mathrm{OneVectors}_{A,j}\) for all \(j \in [1 \mathinner{.\,.}d]\) and the strings \(\mathrm{OnePos}_{a_i}\) for all \(i \in [1 \mathinner{.\,.}n]\). Using these strings, we can then compute \(|U_{A,i}|\) for every \(i \in [1 \mathinner{.\,.}n]\) in \(\mathcal{O}(d)\) time. In total, computing \(A_{\rm len}\) takes \(\mathcal{O}(dn)\) time. Using \(A_{\rm len}\), we can obtain \(A_{\rm sum}\) in \(\mathcal{O}(n)\) time. In total, construction of \(A_{\rm sum}\) takes \(\mathcal{O}(dn)\) time. Observe that, by 15, for any \(i \in [1 \mathinner{.\,.}n]\), we then have \[U_{A}(A_{\rm sum}[i-1] \mathinner{.\,.}A_{\rm sum}[i]] = U_{A,i}.\]

3. Using 15, in \(\mathcal{O}(dn)\) time we construct an SLG \(G = (V, \Sigma, R, S)\) such that \(\Sigma = \{1, \dots, \sigma\}\) (where \(\sigma = n\)) and \(L(G) = \{T\}\), where \(T = U_{A}\) (15). Note that the upper bound on the runtime of 15 implies that \(|G| = \mathcal{O}(dn)\). Denote \(N = |T|\) and note that by 14, it holds \(N \leq dn^2\). Recall that above we also noted that \(N \geq n\) (which, together with \(N \leq dn^2\), implies that \(\log N = \Theta(\log n)\)). Since \(\sigma = n\), we thus obtain \(N \leq d\sigma^2\), i.e., \(\sigma = \Omega((N/d)^{1/2}) = \Omega((N/\log n)^{1/2}) = \Omega((N/\log N)^{1/2})\). Note also that by \(|G| = \mathcal{O}(dn)\), it follows that \(n = \Omega(|G| / d) = \Omega(|G| / \log n) = \Omega(|G| / \log N)\).

4. In this step, we determine whether there exist \(i,j \in [1 \mathinner{.\,.}n]\) such that \(\left\langle a_i, a_j \right\rangle = 0\). By 6, this reduces to checking whether there exists \(i \in [1 \mathinner{.\,.}n]\) such that \(\mathrm{distinct}_{U_{A,i}}(0, |U_{A,i}|) < n\) (see 4 15). We thus proceed as follows. Using the array \(A_{\rm sum}\), in \(\mathcal{O}(n)\) time, we prepare arguments for a batch of \(m = n = \Omega(|G| / \log N)\) range distinct counting queries on \(T\). More precisely, the \(i\)th query is to compute \(\mathrm{distinct}_{T}(A_{\rm sum}[i-1], A_{\rm sum}[i])\). We return yes if and only if at least one returned value is smaller than \(n\). Answering this batch of queries takes \[\begin{align} \mathcal{O}(m|G|^{1-\epsilon} \log^{c'} N) \subseteq \mathcal{O}(n \cdot (dn)^{1-\epsilon} \log^{c'} n) = \mathcal{O}(n^{2-\epsilon} \cdot \log^{1+c'-\epsilon} n) \subseteq \mathcal{O}(n^{2-\epsilon'}) \end{align}\] time.

In total, the algorithm takes \(\mathcal{O}(dn + n^{2-\epsilon'}) = \mathcal{O}(n^{2-\epsilon'})\) time. Note that since our choice of \(\epsilon'\) works for all \(c\), we have thus proved that 7 does not hold. ◻

Proof. The proof is analogous to the proof of 14. ◻

Proof. We first establish an auxiliary property. Observe that, for every \(p \in [1 \mathinner{.\,.}d]\), all symbols in the string \(\mathrm{ZeroVectors}_{A,p}\) (16) are distinct. By 17, this implies that, for every \(i, j \in [1 \mathinner{.\,.}n]\), the symbol \(j\) occurs in the string \(W_{A,i}\) at most \(|\mathrm{OnePos}_{a_i}|\) times. Consequently, we obtain that the symbol \(j\) appears in the string \(W_{A,i}\) \(|\mathrm{OnePos}_{a_i}|\) times if and only if, letting \(R = \mathrm{OnePos}_{a_i}\) and \(k = |R|\), the symbol \(j\) appears in the string \(\mathrm{ZeroVectors}_{A,R[t]}\) for all \(t \in [1 \mathinner{.\,.}k]\).

([lm:reduce-ov-to-range-mode-freq-it-1]) \(\Rightarrow\) ([lm:reduce-ov-to-range-mode-freq-it-2]) Assume that \(\left\langle a_i, a_j \right\rangle \neq 0\). Then, there exists \(p \in [1 \mathinner{.\,.}d]\) such that \(a_i[p] = {\tt 1}\) and \(a_j[p] = {\tt 1}\). By 14, \(p\) appears in \(\mathrm{OnePos}_{a_i}\), i.e., letting \(R = \mathrm{OnePos}_{a_i}\) and \(k = |R|\), it holds \(R[t] = p\) for some \(t \in [1 \mathinner{.\,.}k]\). On the other hand, \(a_j[p] = {\tt 1}\) implies, by 16, that \(j\) does not occur in \(\mathrm{ZeroVectors}_{A,p} = \mathrm{ZeroVectors}_{A,R[t]}\). By the above auxiliary property, we thus obtain that \(j\) appears in \(W_{A,i}\) less than \(|\mathrm{OnePos}_{a_i}|\) times.

([lm:reduce-ov-to-range-mode-freq-it-2]) \(\Rightarrow\) ([lm:reduce-ov-to-range-mode-freq-it-1]) Assume that the symbol \(j\) occurs in \(W_{A,i}\) less than \(|\mathrm{OnePos}_{a_i}|\) times. By the above auxiliary property, this implies that, letting \(R = \mathrm{OnePos}_{a_i}\) and \(k = |R|\), there exists \(t \in [1 \mathinner{.\,.}k]\) such that \(j\) does not occur in \(\mathrm{ZeroVectors}_{A,R[t]}\). By 16, this implies that it holds \(a_{j}[R[t]] = {\tt 1}\). On the other hand, note that, by \(R = \mathrm{OnePos}_{a_i}\) and 14, it holds \(a_{i}[R[t]] = {\tt 1}\). Combining this, we thus obtain that \(\left\langle a_i, a_j \right\rangle \neq 0\). ◻

Proof. Note that, for every \(i \in [1 \mathinner{.\,.}n]\), the string \(W_{A,i}\) (17) is over alphabet \(\{1, \ldots, n\}\). Thus, by 7, we obtain that \[\{j \in [1 \mathinner{.\,.}n] : j\text{ occurs in }W_{A,i}\text{ at least }|\mathrm{OnePos}_{a_i}|\text{ times}\} = \{j \in [1 \mathinner{.\,.}n] : \left\langle a_i, a_j \right\rangle = 0\}. \qedhere\] ◻

Proof. The proof is analogous to the proof of 15. ◻

Proof. Suppose that there exists a constant \(\epsilon > 0\) such that, given any SLG \(G = (V, \Sigma, R, S)\) representing a string \(T \in \Sigma^{N}\) (where \(\Sigma = \{1, \ldots, \sigma\}\) and \(\sigma = \Omega((N / \log N)^{1/2})\)), we can answer any batch of \(m = \Omega(|G| / \log N)\) range mode frequency queries in \(\mathcal{O}(m|G|^{1-\epsilon} \log^{c'} N)\) time, where \(c' > 0\) is some constant. We will show that this implies that 7 does not hold.

Denote \(\epsilon' = \epsilon/2\). Consider any sequence \(A = (a_1, \ldots, a_n)\) of \(n \geq 2\) binary vectors of dimension \(d = c\log n\), where \(c \geq 1\) is a constant. Given the sequence \(A\), we determine whether there exist \(i,j \in [1 \mathinner{.\,.}n]\) such that \(\left\langle a_i, a_j \right\rangle = 0\) as follows:

1. In \(\mathcal{O}(dn)\) time we check whether for all \(i \in (1 \mathinner{.\,.}n]\) it holds \(a_i = a_1\). If yes, then we are able to solve this OV instance simply by checking if \(a_1 = {\tt 0}^{d}\), and this check concludes the algorithm. Let us thus assume that there exists \(i \in (1 \mathinner{.\,.}n]\) such that \(a_i \neq a_1\), i.e., not all vectors in the input sequence are equal. Then, there exists \(j \in [1 \mathinner{.\,.}d]\) such that for some \(i, i' \in [1 \mathinner{.\,.}n]\) it holds \(a_{i}[j] = {\tt 0}\) and \(a_{i'}[j] = {\tt 1}\). Denote \(n_0 = |\{i \in [1 \mathinner{.\,.}n] : a_{i}[j] = {\tt 0}\}|\) and \(n_1 = n - n_0\). Note that it holds \(n_1 \geq 1\) and \(|\mathrm{ZeroVectors}_{A,j}| = n_0 \geq 1\). Since for every \(i \in [1 \mathinner{.\,.}n]\) satisfying \(a_i[j] = {\tt 1}\), the string \(\mathrm{ZeroVectors}_{A,j}\) is a substring of \(W_{A,i}\) (see 17), it follows that for every such index \(i\), it holds \(|W_{A,i}| \geq n_0\). Since there are \(n_1\) such indices \(i\), we thus obtain \[|W_{A}| = \textstyle\sum_{i=1}^{n} |W_{A,i}| \geq n_1 \cdot n_0.\] By \(n_0 \geq 1\), \(n_1 \geq 1\), and \(n_0 + n_1 = n\), we thus obtain \(|W_{A}| \geq n - 1\).

2. In \(\mathcal{O}(dn)\) time we compute an array \(A_{\rm ones}[1 \mathinner{.\,.}n]\) defined by \(A_{\rm ones}[i] = |\mathrm{OnePos}_{a_i}|\).

3. Next, we compute an array \(A_{\rm sum}[0 \mathinner{.\,.}n]\) defined such that \(A_{\rm sum}[0] = 0\) and, for every \(i \in [1 \mathinner{.\,.}n]\), \(A_{\rm sum}[i] = \sum_{j=1}^{i} |W_{A,j}|\) (see 17). The algorithm proceeds analogously as in the proof of [th:hardness-of-range-distinct-count]. Observe that, by 17, for any \(i \in [1 \mathinner{.\,.}n]\), we then have \[W_{A}(A_{\rm sum}[i-1] \mathinner{.\,.}A_{\rm sum}[i]] = W_{A,i}.\]

4. Using 17, in \(\mathcal{O}(dn)\) time we construct an SLG \(G = (V, \Sigma, R, S)\) such that \(\Sigma = \{1, \dots, \sigma\}\) (where \(\sigma = n\)) and \(L(G) = \{T\}\), where \(T = W_{A}\) (17). Note that the upper bound on the runtime of 17 implies that \(|G| = \mathcal{O}(dn)\). Denote \(N = |T|\) and note that by 16, it holds \(N \leq dn^2\). Recall that above we also noted that \(N \geq n-1\) (which, together with \(N \leq dn^2\), implies that \(\log N = \Theta(\log n)\)). Since \(\sigma = n\), we thus obtain \(N \leq d\sigma^2\), i.e., \(\sigma = \Omega((N/d)^{1/2}) = \Omega((N/\log n)^{1/2}) = \Omega((N/\log N)^{1/2})\). Note also that by \(|G| = \mathcal{O}(dn)\), it follows that \(n = \Omega(|G| / d) = \Omega(|G| / \log n) = \Omega(|G| / \log N)\).

5. In this step, we determine whether there exist \(i,j \in [1 \mathinner{.\,.}n]\) such that \(\left\langle a_i, a_j \right\rangle = 0\). By 8, this reduces to checking whether there exists \(i \in [1 \mathinner{.\,.}n]\) such that it holds \(\mathrm{mode-freq}_{W_{A,i}}(0,|W_{A,i}|) \geq A_{\rm ones}[i]\) (see 5 17). We thus proceed as follows. Using the array \(A_{\rm sum}\), in \(\mathcal{O}(n)\) time, we prepare arguments for a batch of \(m = n = \Omega(|G| / \log N)\) range mode frequency queries on \(T\). More precisely, the \(i\)th query is to compute \(\mathrm{mode-freq}_{T}(A_{\rm sum}[i-1],A_{\rm sum}[i])\). We return yes if and only if at least one returned value is at least the corresponding value \(A_{\rm ones}[i]\). Answering this batch of queries takes \[\begin{align} \mathcal{O}(m|G|^{1-\epsilon} \log^{c'} N) \subseteq \mathcal{O}(n \cdot (dn)^{1-\epsilon} \log^{c'} n) = \mathcal{O}(n^{2-\epsilon} \cdot \log^{1+c'-\epsilon} n) \subseteq \mathcal{O}(n^{2-\epsilon'}) \end{align}\] time.

In total, the algorithm takes \(\mathcal{O}(dn + n^{2-\epsilon'}) = \mathcal{O}(n^{2-\epsilon'})\) time. Note that since our choice of \(\epsilon'\) works for all \(c\), we have thus proved that 7 does not hold. ◻

Proof. Denote \(V = \{N_1, \ldots, N_{g}\}\). Assume that the definitions of all nonterminals in \(G\) are represented using an array \(A_{\rm rhs}[1 \mathinner{.\,.}g]\) defined such that, for every \(i \in [1 \mathinner{.\,.}g]\),

• If \(|\mathrm{rhs}_{G}(N_i)| = 1\), then \(A_{\rm rhs}[i] = \mathrm{rhs}_{G}(N_i) \in [1 \mathinner{.\,.}\sigma]\).

• Otherwise \(A_{\rm rhs}[i] = (i', i'')\), where \(i', i'' \in [1 \mathinner{.\,.}g]\) are such that \(\mathrm{rhs}_{G}(N_i) = N_{i'} N_{i''}\).

The algorithm to compute \(\mathrm{distinct}_{T}(b, e)\) proceeds as follows:

1. In the first step we construct a directed graph \(D = (V', E')\), where \(V' = \{0,1,\ldots,g+\sigma\}\) and the set of directed edges \(E'\) is defined such that, for every \((u,v) \in V'^2\), \((u,v) \in E'\) holds if and only if \(u \in [1 \mathinner{.\,.}g]\) and one of the following two conditions hold:

   • \(|\mathrm{rhs}_{G}(N_u)| = 2\) and, letting \((i',i'') = A_{\rm rhs}[u]\), it holds either \(v = i'\) or \(v = i''\),

   • \(|\mathrm{rhs}_{G}(N_u)| = 1\), and, letting \(c = \mathrm{rhs}_{G}(N_u)\), it holds \(v = g + c\).

   Given the array \(A_{\rm rhs}[1 \mathinner{.\,.}g]\), the computation of \(D\) takes \(\mathcal{O}(|G|)\) time.

2. Next, we compute an array \(A_{\rm explen}[1 \mathinner{.\,.}g]\) defined such that, for every \(i \in [1 \mathinner{.\,.}g]\), \(A_{\rm explen}[i] = |\mathrm{exp}_{G}(N_i)|\). Given the array \(A_{\rm rhs}\), computing \(A_{\rm explen}\) takes \(\mathcal{O}(|G|)\) time.

3. We use the array \(A_{\rm rhs}\) and \(A_{\rm explen}\) to compute a sequence \((a_i)_{i \in [1 \mathinner{.\,.}k]}\) of integers in \([1 \mathinner{.\,.}g]\) that satisfies

   • \(k = \mathcal{O}(\log n)\) and

   • \(T(b \mathinner{.\,.}e] = \bigodot_{i=1,\ldots,k} \mathrm{exp}_{G}(N_{a_i})\).

   It is easy to see that such a sequence exists since \(G\) has height \(h = \mathcal{O}(\log n)\). After computing the sequence \((a_i)_{i \in [1 \mathinner{.\,.}k]}\), we update the graph \(D\) by adding to \(E'\) the set of edges \(\{(0,a_i) : i \in [1 \mathinner{.\,.}k]\}\). This step takes \(\mathcal{O}(k) = \mathcal{O}(\log n) = \mathcal{O}(|G|)\) time (see 3).

4. We perform a depth-first search in \(D\) from vertex \(0\) marking all reachable vertices, and finally, count how many vertices among those in the subset \(\{g+1,\ldots,g+\sigma\}\) were reachable, and return that as the answer. This step takes \(\mathcal{O}(|V'| + |E'|) = \mathcal{O}(|G|)\) time.

In total, the algorithm takes \(\mathcal{O}(|G|)\) time. ◻

Proof. Denote \(V = \{N_1, \ldots, N_{g}\}\). Assume that the definitions of all nonterminals in \(G\) are represented using an array \(A_{\rm rhs}[1 \mathinner{.\,.}g]\) defined such that, for every \(i \in [1 \mathinner{.\,.}g]\),

• If \(|\mathrm{rhs}_{G}(N_i)| = 1\), then \(A_{\rm rhs}[i] = \mathrm{rhs}_{G}(N_i) \in \Sigma\).

• Otherwise \(A_{\rm rhs}[i] = (i', i'')\), where \(i', i'' \in [1 \mathinner{.\,.}g]\) are such that \(\mathrm{rhs}_{G}(N_i) = N_{i'} N_{i''}\).

We also denote \(\Sigma_{T} = \{T[i] : i \in [1 \mathinner{.\,.}n]\}\).

The algorithm to compute \(\mathrm{distinct}_{T}(b, e)\) proceeds as follows:

1. In this step, we compute an array \(A'_{\rm rhs}[1 \mathinner{.\,.}g]\) defined such that, for every \(i \in [1 \mathinner{.\,.}g]\),

   • If \(|\mathrm{rhs}_{G}(N_i)| = 1\), then \(A'_{\rm rhs}[i] = |\{c \in \Sigma_{T} : c \preceq \mathrm{rhs}_{G}(N_i)\}| \in [1 \mathinner{.\,.}|\Sigma_{T}|]\).

   • Otherwise, \(A'_{\rm rhs}[i] = A_{\rm rhs}[i]\).

   To compute the array \(A'_{\rm rhs}\), we first lexicographically sort all the pairs in the set \(\{(\mathrm{rhs}_{G}(N_i), i) : i \in [1 \mathinner{.\,.}g]\text{ and }|\mathrm{rhs}_{G}(N_i)| = 1\}\) (which is easy to obtain from \(A_{\rm rhs}\) in \(\mathcal{O}(|G|)\) time) in \(\mathcal{O}(|G| \log |G|) = \mathcal{O}(|G| \log n)\) time. With one more scan of this sorted sequence, it is straightforward to compute the array \(A'_{\rm rhs}\) in \(\mathcal{O}(|G|)\) time.

2. Let \(G'\) denote an SLP obtained from \(G\) by replacing all the rules (represented in array \(A_{\rm rhs}\)) with rules represented in \(A'_{\rm rhs}\), and let \(T'\) be the string represented by \(G'\). The resulting grammar is over alphabet \(\Sigma' = [1 \mathinner{.\,.}|\Sigma_{T}|]\) which satisfies \(|\Sigma'| \leq |G| = |G'|\). Since \(T'\) is obtained from \(T\) by a one-to-one renaming of symbols, \(\mathrm{distinct}_{T}(b, e) = \mathrm{distinct}_{T'}(b, e)\). Thus, using 18, we can compute \(\mathrm{distinct}_{T'}(b, e)\) in \(\mathcal{O}(|G|)\) time.

In total, the algorithm takes \(\mathcal{O}(|G| \log n)\) time. ◻

Proof. The algorithm to compute \(\mathrm{distinct}_{T}(b, e)\) proceeds as follows:

1. Using 2, in \(\mathcal{O}(|G|)\) time, compute an SLP \(G' = (V', \Sigma, R', S')\) such that \(L(G') = L(G) = \{T\}\). Note that the upper bound on the runtime of 2 implies that \(|G'| = \mathcal{O}(|G|)\).

2. Using 1, in \(\mathcal{O}(|G|)\) time, compute an SLP \(G'' = (V'', \Sigma, R'', S'')\) of height \(h = \mathcal{O}(\log n)\) such that \(L(G'') = L(G') = \{T\}\). Similarly as above, note that \(|G''| = \mathcal{O}(|G'|) = \mathcal{O}(|G|)\).

3. Apply 19 to \(G''\) to compute \(\mathrm{distinct}_{T}(b, e)\) in \(\mathcal{O}(|G''| \log n) = \mathcal{O}(|G| \log n)\) time.

In total, the algorithm takes \(\mathcal{O}(|G| \log n)\) time. ◻