# Text Indexing for Regular Expression Matching
## 2 Hardness of Creating an Index for Regular Expression Queries
### Hardness Based on OMM  
We will now utilize the OMM conjecture to strengthen our results. The reduction in this section requires only a single query pattern of size \(\Theta(n^{2})\). This allows us to obtain a lower bound stronger than those obtained under OMV or 3 SUM, but still conditioned on a plausible conjecture. See Section 1 for a description of the OMM conjecture.  
Again, let \(r^{1},\ldots,r^{n}\) be the rows of the input matrix \(A\) that we can preprocess. We make \(T=2\circ r^{1}\circ 1^{n}\circ 2\circ r^{2}\circ 1^{n}\circ\ldots\circ 2 \circ r^{n}\circ 1^{n}\). The substrings \(1^{n}\) will allow us to deduce from each ending index of a match the vector \(v^{j}\) used in the construction of \(p\) that is responsible for that match. As we will see, this is since a subexpression in \(p\) built from a vector \(v^{j}\) has the suffix \(1^{j}\). Note that \(|T|=\Theta(n^{2})\).  
From the matrix \(B\) supplied at run time, we construct a regular expression \(p\). Let \(B\) have the columns \(v^{1}\), \(\ldots\), \(v^{n}\) from left to right. Using the same vector gadgets from Section 2.1, we set \(p=\left(2\circ VG(v^{1})\circ 1\right)\left|\left(2\circ VG(v^{2})\circ 1^{2} \right)\right|\ldots\left|\left(2\circ VG(v^{n})\circ 1^{n}\right)\).  
**Lemma 2**.: _For \(i,j\in[1,n]\) there exists a substring matched by regular expression \(p\) starting in \(T\) at index \((i-1)(2n+1)+1\) and a substring matched ending at index \((i-1)(2n+1)+1+n+j\) iff \(C_{ij}=0\) where \(AB=C\)._  
Proof.: First assume \(C_{ij}=0\). This implies that \(r^{i}\cdot v^{j}=0\). By the argument given in the proof for Lemma 1, this implies the subexpression \(2\circ VG(v^{j})\) matches the substring \(2\circ r^{i}\) of \(T\), which now starts at index \((i-1)(2n+1)+1\). Moreover, we can match the subexpression \(1^{j}\) of \(2\circ VG(v^{j})\circ 1^{j}\) with the first \(j\)\(1^{\prime}\)s that follow \(2\circ r^{i}\) in \(T\), giving the final index of the match as \((i-1)(2n+1)+1+n+j\).  
To prove the converse, assume \(C_{ij}=1\). This implies \(r^{i}\cdot v^{j}\
eq 0\). By the argument given in Lemma 1, this implies that \(2\circ r^{i}\) cannot be matched with \(2\circ VG(v^{j})\). Furthermore, for any \(k\
eq j\), if \(2\circ VG(v^{k})\) matches \(2\circ r^{i}\), then the final index of substring matching \(2\circ VG(v^{k})\circ 1^{k}\) and starting at \((i-1)(2n+1)+1+n+k\), rather than \((i-1)(2n+1)+1+n+j\). Hence, there can not be both a match starting at \((i-1)(2n+1)+1\) and a matching ending at \((i-1)(2n+1)+1+n+j\).  
The output size of the query is bound by \(n^{2}\) since each of the \(n\) subexpressions of \(p\) of form \(2\circ VG(v^{j})\circ 1^{j}\) match \(T\) in at most \(n\) places. Because the output size does not exceed our desired lower bound we can apply Lemma 2 and the fact that \(|p|=\Theta(n^{2})\) to obtain Theorem 2.  
**Theorem 2**.: _For all \(\varepsilon>0\), conditioned on the OMM conjecture, there does not exist an index that can answer regular expression queries in \(O((|T|+|p|+occ)^{3/2-\varepsilon})\), where \(occ\) is the size of the output. This holds even with arbitrary polynomial-time preprocessing._