## 8 Discussion  
Using PAAs, we have shown how the exact distribution of the number of character accesses for window-based pattern matching algorithms can be computed algorithmically. The framework admits general finite-memory text models, including i.i.d. models, Markov models of arbitrary order, and character-emitting hidden Markov models. The given construction results in an asymptotic runtime of \(O(n^{2}\cdot m\cdot|\mathcal{Q}^{\mathcal{D}}|\cdot|\mathcal{C}|^{2}\cdot| \Sigma|)\). The number of DAA states \(|\mathcal{Q}^{\mathcal{D}}|\) can be as large as \(O(m\cdot\Sigma^{m})\), but we conjecture that for each reasonable algorithm, the necessary minimal state set \(\mathcal{Q}^{\mathcal{D}}_{\min}\) grows only polynomially with \(m\). In particular, we conjecture \(O(m^{3})\) sizes for B(N)DM and BOM; this is consistent  
\begin{table}
\begin{tabular}{c c c c} \hline \hline \multirow{2}{*}{\(m\)} & **States unminimized** & **States minimized (min./avg./max.)** \\ \cline{2-4}  & \(|\Sigma|^{m}\cdot(m+1)\) & **Horspool** & **BOM** & **B(N)DM** \\ \hline
2 & 48 & 4 / 4.8 / 5 & 4 / 4.0 / 4 & 4 / 4.8 / 5 \\
3 & 256 & 7 / 8.3 / 9 & 7 / 8.3 / 9 & 7 / 9.6 / 10 \\
4 & 1280 & 11 / 14.3 / 15 & 11 / 15.6 / 18 & 11 / 17.0 / 19 \\
5 & 6144 & 16 / 23.6 / 25 & 16 / 26.5 / 30 & 16 / 27.9 / 31 \\
6 & 28672 & 22 / 37.0 / 39 & 22 / 41.8 / 47 & 22 / 42.8 / 48 \\
7 & 131072 & 29 / 55.2 / 58 & 29 / 62.4 / 70 & 29 / 62.6 / 70 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Comparison of DAA sizes for all patterns of length \(m\) over \(\Sigma=\{\texttt{A},\texttt{C},\texttt{G},\texttt{T}\}\).  
Figure 6: Histogram on number of states of minimal DAAs over all patterns of length 6 over \(\Sigma=\{\texttt{A},\texttt{C},\texttt{G},\texttt{T}\}\).  
with the numbers in Table 1. For Horspool, a specialized \(O(m^{2})\) construction is known [13]. Otherwise, in practice, the DAA size can be reduced by DAA minimization, but it remains open if there exists an algorithm to construct the minimal automaton directly in general, _i.e._, using only \(O(|\mathcal{Q}_{\mathrm{min}}^{\mathcal{D}}|)\) time. A proof that this is the case for a broad class of pattern matching algorithms would be an important insight into the nature of these algorithms and therefore certainly warrants further research.  
The behavior of BOM deserves further attention: first, periodic zero probabilities are found in its distribution of text character accesses; and second, it may (unexpectedly) need fewer text accesses than B(N)DM on some patterns, although BOM's shift values are never better than B(N)DM's.  
We focused on algorithms for single patterns, but the presented techniques also apply to algorithms to search for multiple patterns like the Wu-Manber algorithm [25] or \"set backward oracle matching\" and \"multiple BNDM\", as described in [8]. A comparison of the resulting distributions could yield new insights into these algorithms as well.  
Other metrics than text character accesses might be of interest and could be easily substituted; for example, just counting the number of windows by defining \(\xi^{p}(w)=1\) for all \(w\in\Sigma^{m}\).  
The given constructions allow us to analyze an algorithm's performance for each pattern individually. While this is desirable for detailed analysis, the cost distribution resulting from randomly choosing text _and_ pattern would also be of interest.  
The results of this paper were obtained while [PERSON] was a PhD student with [PERSON] and TU Dortmund. The thesis is available at [[http://hdl.handle.net/2003/27760](http://hdl.handle.net/2003/27760)]([http://hdl.handle.net/2003/27760](http://hdl.handle.net/2003/27760)).