# Text Indexing for Regular Expression Matching
## 3 A Regular Expression Index
### Querying Matches via Graph Traversal
#### 3.4.1 Restricted Regular Expressions  
If we restrict ourselves to patterns with only **concatenation** and **or** operators (_restricted regular expressions_), using breadth-first-search all'start' vertices of a subgraph are reached on the same level of the search. Hence for restricted regular expressions, we can better utilize the Boolean matrix representations of subgraphs, taking advantage of techniques developed for performing this multiplication more efficiently. Based on whether we desire a deterministic solution or a solution that is correct whp we obtain different space and preprocessing times. Lemma 4 (Williams [34]): _For all \(\varepsilon\in(0,1/2)\), every \(n\times n\) Boolean matrix \(A\) can be preprocessed in \(O(n^{2+\varepsilon})\) time such that every subsequent multiplication of \(A\) with an arbitrary Boolean \(n\)-vector \(x\) can be performed in \(O(n^{2}/(\varepsilon\log n)^{2})\) time, on a pointer machine or a \((\log n)\)-word RAM._  
Applying Lemma 4 with \(\varepsilon=1/4\), the query time complexity becomes  
\[\frac{|T||p|}{\tau}+\frac{|p|}{\tau}\cdot\frac{|T|^{2}}{\log^{2}|T|}=O\Bigg{(} \frac{|T||p|}{\tau}\Bigg{(}1+\frac{|T|}{\log^{2}|T|}\Bigg{)}\Bigg{)}.\]  
We again reparameterize, setting \(\tau^{\prime}=\Theta\Bigg{(}\tau\bigg{(}1+\frac{|T|}{\log^{2}|T|}\bigg{)}^{-1 }\Bigg{)}\). The query time becomes \(O(\frac{|T||p|}{\tau^{\prime}})\). The space complexity goes from \(|T|^{2}2^{O(\tau)}\) to \(\operatorname{Exp}\bigg{(}\tau^{\prime}\frac{|T|}{\log^{2}|T|}\bigg{)}\) and the preprocessing time goes from \(|T|^{2+\varepsilon}2^{O(\tau)}\) to \(\operatorname{Exp}\bigg{(}\tau^{\prime}\frac{|T|}{\log^{2}|T|}\bigg{)}\). The parameter \(\tau^{\prime}\) ranges from \(1\) to \(|T|\). Theorem 4: _For constant sized alphabets and some parameter \(\tau\in[1,|T|]\) fixed at construction, for patterns \(p\) containing only 'concatenation' and 'or' operators, there exists a data structure which answers regular expression existential queries in time \(O\Big{(}\frac{|T|\cdot|p|}{\tau}\Big{)}\) requiring \(\operatorname{Exp}\bigg{(}\tau\cdot\frac{|T|}{\log^{2}|T|}\bigg{)}\) space and preprocessing time._  
The techniques of [PERSON] and [PERSON] in [20] yield a randomized solution with better preprocessing time and space. Lemma 5 ([20]): _With no preprocessing of the matrix \(A\in\{0,1\}^{n\times n}\) and for any sequence of \(t=2^{\omega(\sqrt{\log n})}\) vectors \(v_{1},...,v_{t}\in\{0,1\}^{n}\), online matrix-vector multiplication of \(A\) and \(v_{i}\) over the Boolean semiring can be performed in \(n^{2}/2^{\Omega(\sqrt{\log n})}\) amortized time, with a randomized algorithm that succeeds whp._  
Given a set of start vertices represented as a binary vector, this allows us to obtain the reachable end vertices using a randomized algorithm running in \(|T|^{2}/2^{\Omega(\sqrt{\log|T|})}\) amortized time over \(2^{\omega(\sqrt{\log|T|})}\) queries that succeeds whp. For each matrix constructed, we apply \(|T|=2^{\omega(\sqrt{\log|T|})}\) multiplications against random binary vectors in preprocessing. The added time complexity of this operation is \(O(|T|^{3})\) in total per matrix. This step is necessary to ensure the amortization techniques used in [20] will work. The traversal is done in the same way as in the deterministic solution, only that each matrix-vector multiplication is repeated multiple times, and the most frequent of these solutions is taken as the output vector. We will show that under the conditions of \(|P|\leq|T|^{z}\) for some \(z=2^{o(\sqrt{\log|T|})}\), to maintain high probability of success of the overall algorithm it is sufficient to perform \(z\cdot\log|T|\) repetitions of each matrix multiplication. Therefore, each matrix during a query requires \((z\cdot|T|^{2}\log|T|)/2^{\Omega(\sqrt{\log|T|})}\) time. That yields an amortized query time of  
\[\frac{|T||p|}{\tau}+\frac{|p|}{\tau}\cdot\frac{z\cdot|T|^{2}\log|T|}{2^{\Omega (\sqrt{\log|T|})}}=O\Bigg{(}\frac{|T||p|}{\tau}\Bigg{(}1+\frac{|T|}{2^{\Omega( \sqrt{\log|T|})}}\Bigg{)}\Bigg{)}\]  
where queries succeed whp.