## 4 Constructing DAAs for Pattern Matching Analysis  
For a given algorithm and pattern \(p\in\Sigma^{m}\) with known shift and cost functions, \(\mathit{shift}^{\,p}:\Sigma^{m}\rightarrow\{1,\ldots,m\}\), \(w\mapsto\mathit{shift}^{\,p}(w)\) and \(\xi^{p}:\Sigma^{m}\rightarrow\mathbb{N}\), \(w\mapsto\xi^{p}(w)\), we construct a DAA that upon reading a text \(s\in\Sigma^{*}\) computes the total cost, defined as the sum of costs over all examined windows. (Which windows are examined depends of course on the shift values of previously examined windows.) Slightly abusing notation, we write \(\xi^{p}(s)\) for the total cost incurred on \(s\). While different constructions are possible (see also [18]), the construction presented here has the advantage that it is simple to describe and implement and processes only one text character at a time. This property allows the construction of a product DAA that directly compares two algorithms as detailed in Section 6. **Definition 2** (DAA encoding a pattern matching algorithm): _Given a window-based pattern matching algorithm \(A\), a pattern \(p\in\Sigma^{m}\), and the associated shift and cost functions, \(\mathit{shift}^{\,p}:\Sigma^{m}\rightarrow\{1,\ldots,m\}\) and \(\xi^{p}:\Sigma^{m}\rightarrow\mathbb{N}\), the DAA encoding algorithm \(A\) is defined by_  
* \(\mathcal{Q}:=\Sigma^{m}\times\{0,\ldots,m\}\)_,_
* \(q_{0}:=(p,m)\)_,_  
_where informally, a state \(q=(w,x)\) means that the last \(m\) read characters spell \(w\) and that \(x\) more characters need to be read to get to the end of the current window. For the start state \(q_{0}=(p,m)\), the component \(p\) is arbitrary, as we need to read \(m\) characters to reach the end of the first window._  
_The remaining components are defined as_  
* \(\mathcal{V}:=\mathbb{N}\)_,_
* \(v_{0}:=0\)_,_
* \(\mathcal{E}:=\{1,\ldots,m\}\)_,_
* \(\eta_{(w,x)}:= \begin{cases}0&\text{ if }x>0,\\ \xi^{p}(w)&\text{ if }x=0,\end{cases} \)__
* \(\theta_{q}:(v,e)\mapsto v+e\) _for all_ \(q\in\mathcal{Q}\) _(addition),_
* \(\delta:\big{(}(w,x),\sigma\big{)}\mapsto \begin{cases}(w^{\prime}\sigma,\,x-1)& \text{ if }x>0,\\ (w^{\prime}\sigma,\mathit{shift}^{\,p}(w)-1)&\text{ if }x=0,\end{cases} \) _where_ \(w^{\prime}\) _is the length-_\((m-1)\) _suffix of_ \(w\)_, i.e.,_ \(w^{\prime}:=w[1]\ldots w[m-1]\)_._  
Figure 2 shows an example of how a DAA for [PERSON]'s algorithm moves from state to state. The value accumulates the cost of examined windows. Therefore, the operation is a simple addition in each state, and the emission of state \((w,x)\) specifies the cost to add. Consequently, the emission is zero if the state does not correspond to an examined window (\(x>0\)), and the emission equals the window cost \(\xi^{p}(w)\) if \(x=0\). The transition function \(\delta\) specifies how to move from one state to the next when reading the next text character \(\sigma\in\Sigma\): In any case, the window content is updated by forgetting the first character and appending the read \(\sigma\). If the end of the current window has not been reached (\(x>0\)), the counter \(x\) is decremented. Otherwise, the window's shift value is used to compute the number of characters till the next window aligns. **Theorem 1**: _Let \(\mathcal{D}\) be a DAA as given by Definition 2. Then, \(\text{value}_{\mathcal{D}}(s)=\xi^{p}(s)\) for all \(s\in\Sigma^{*}\)._  
ProofThe total cost \(\xi^{p}(s)\) can be written as the sum of costs of all processed windows: \(\xi^{p}(s)=\sum_{i\in I_{s}}\xi^{p}(s[i-m+1\ldots i])\), where \(I_{s}\) is the set of indices giving the processed windows, _i.e._, \(I_{s}\subset\{m-1,\ldots,|s|-1\}\) such that  
\[i\in I_{s}\quad:\Longleftrightarrow\quad i=m-1\quad\text{or}\quad\exists j \in I_{s}:i=j+\text{shift}\,^{p}(s[j-m+1\ldots j]).\]  
We have to prove that the DAA computes this value for \(s\in\Sigma^{*}\). Let \((w_{i},x_{i})\) be the DAA state active after reading \(s[..i]\).