## 4 Constructing DAAs for Pattern Matching Analysis
Observe that the transition function \(\delta\) ensures that the \(w_{i}\)-component of \((w_{i},x_{i})\) reflects the rightmost length-\(m\) window of \(s[..i]\), which can immediately be verified inductively. Thus, the emission on reading the last character \(s[i]\) of \(s[..i]\) with \(i\geq m-1\) is, by definition of \(\eta_{(w_{i},x_{i})}\), either \(\xi^{p}(s[i-m+1\ldots i])\) or zero, depending on the second component of \((w_{i},x_{i})\). As the operation is an addition for all states, \(\text{value}_{\mathcal{D}}(s)=\sum_{i\in I_{s}^{\prime}}\xi^{p}(s[i-m+1\ldots i])\) for  
\[I_{s}^{\prime}:=\big{\{}i\in\{0,\ldots,|s|-1\}:x_{i}=0\big{\}}.\]  
It remains to show that \(I_{s}=I_{s}^{\prime}\). To this end, note that by \(\delta\), we have \(x_{i+1}=x_{i}-1\) if \(x_{i+1}>0\) and \(x_{i+1}=\text{shift}\,^{p}(w_{i})-1\) if \(x_{i+1}=0\). As \(q_{0}=(p,m)\), it follows that \(m-1\in I_{s}^{\prime}\). Using \(w_{i}=s[i-m+1\ldots i]\) for \(i\geq m-1\), we conclude that whenever \(x_{i}=0\), it follows that \(x_{j}=0\) for \(j=i+\text{shift}\,^{p}(s[i-m+1\ldots i])\) and that \(x_{j^{\prime}}>0\) for \(i<j^{\prime}<j\). Hence we obtain that \(i\in I_{s}^{\prime}\) implies that \(i+\text{shift}\,^{p}(s[i-m+1\ldots i])\in I_{s}^{\prime}\) and \(i+k\
otin I_{s}^{\prime}\) for \(0<k<\text{shift}\,^{p}(s[i-m+1\ldots i])\), which completes the proof. \(\Box\)  
DAA Minimization.The size of the constructed DAA's state space is \((m+1)|\Sigma|^{m}\) and grows exponentially with the pattern length, making the application for long patterns infeasible in practice. However, depending on the particular circumstances (_i.e._, algorithm and pattern analyzed), the  
Figure 2: Illustration of the DAA encoding the behavior of [PERSON]’s algorithm when searching the text \(s=CGACATACGA\) for the pattern \(p=\text{ACGA}\). On top, one sees the state the DAA takes after reading the character below. The leftmost state is the start state. At the bottom, the windows considered by [PERSON]’s algorithm are indicated, illustrating that the second component of the current state encodes the distance to the right end of the next window. constructed DAA can often be substantially reduced by state space minimization [21]. For example, for B(N)DM, both cost and shift of an examined window depend only on the longest factor of \(p\) that is a suffix of the window. Since there are only \(O(m^{2})\) different factors, it is reasonable that \(|\Sigma|^{m}\) can be replaced by \(O(m^{2})\), for a total state space of size \(O(m^{3})\). Therefore, for each algorithm, a specialized construction may exist that directly constructs the minimal state space whose size may only grow polynomially with \(m\). For the Horspool algorithm, it is known that the state space has a size of only \(O(m^{2})\), as the construction of Tsai [13] can be adapted to construct a DAA according to our definition. However, we have been unable to provide a direct construction of the minimal DAA applicable to all window-based pattern matching algorithms. [PERSON]'s algorithm [21] minimizes a DFA in \(O(|\mathcal{Q}|\log|\mathcal{Q}|)\) time by iteratively refining a partition of the state set. In the beginning, all states are partitioned into two distinct sets: one containing the accepting states, and the other containing the non-accepting states. This partition is iteratively refined whenever a reason for non-equivalence of two states in the same set is found. Upon termination, the states are partitioned into sets of equivalent states. Refer to [22] for an in-depth explanation of [PERSON]'s algorithm. The algorithm can straightforwardly be adapted to minimize DAAs by choosing the initial state set partition appropriately. In our case, each DAA state is associated with the same operation. The only differences in state's behavior thus stem from different emissions. Therefore, [PERSON]'s algorithm can be initialized by the partition induced by the emissions and then continued as usual. As we exemplify in Section 7, this leads to a considerable reduction of the number of states.