## 5 Probabilistic Arithmetic Automata
### Constructing a PAA from a DAA and a Text Model
Then  
\[f_{t}\big{(}\underbrace{(q^{\mathcal{D}},c)}_{=:q},v\big{)} \tag{4}\] \[= \sum_{q^{\prime}\in\mathcal{Q}}\;\sum_{(v^{\prime},e)\in q_{q}^{ -1}(v)}\;f_{t-1}(q^{\prime},v^{\prime})\cdot T(q^{\prime},q)\cdot\mu_{q}(e)\] (5) \[= \sum_{q^{\prime}\in\mathcal{Q}}\;\sum_{(v^{\prime},e)\in\mathcal{ V}\times\mathcal{E}}\big{[}\!\big{[}\theta_{q^{\mathcal{D}}}^{\mathcal{D}}(v^{ \prime},e)=v\big{]}\!\big{]}\cdot f_{t-1}(q^{\prime},v^{\prime})\cdot T(q^{ \prime},q)\cdot\big{[}\!\big{[}\eta_{q^{\mathcal{D}}}=e\big{]}\!\big{]}\] (6) \[= \sum_{q^{\prime}\in\mathcal{Q}^{\mathcal{D}}}\;\sum_{c^{\prime} \in\mathcal{C}}\;\sum_{(v^{\prime},e)\in\mathcal{V}\times\mathcal{E}}\big{[}\! \big{[}\theta_{q^{\mathcal{D}}}^{\mathcal{D}}(v^{\prime},e)=v\big{]}\!\big{]} \cdot\big{[}\!\big{[}\eta_{q^{\mathcal{D}}}=e\big{]}\!\big{]}\cdot f_{t-1}(q^{ \prime},v^{\prime})\] (7) \[\cdot\sum_{\sigma\in\Sigma}\big{[}\!\big{[}\delta(q^{\mathcal{D}},\sigma)=q^{\mathcal{D}}\big{]}\!\big{]}\cdot\varphi(c^{\prime},\sigma,c)\] \[= \sum_{s\in\Sigma^{t-1}}\;\sum_{\sigma\in\Sigma}\;\sum_{q^{ \prime}\in\mathcal{Q}^{\mathcal{D}}}\;\sum_{c^{\prime}\in\mathcal{C}}\;\sum_{( v^{\prime},e)\in\mathcal{V}\times\mathcal{E}}\big{[}\!\big{[}\theta_{q^{ \mathcal{D}}}^{\mathcal{D}}(v^{\prime},e)=v\big{]}\!\big{]}\cdot\big{[}\!\big{[} \eta_{q^{\mathcal{D}}}=e\big{]}\!\big{]}\] \[\cdot\big{[}\!\delta(q^{\mathcal{D}},\sigma)=q^{\mathcal{D}}\! \big{]}\cdot\big{[}\!\hat{\delta}\big{(}(q_{0}^{\mathcal{D}},v_{0}),s\big{)}=( q^{\prime\mathcal{D}},v^{\prime})\!\big{]}\] (8) \[\cdot\mathbb{P}(S_{0}\ldots S_{t-2}=s,C^{t-1}=c^{\prime})\cdot \varphi(c^{\prime},\sigma,c)\] \[f_{t}\big{(}(q^{\mathcal{D}},c),v\big{)}=\sum_{s\in\Sigma^{t}}\big{[}\hat{ \delta}\big{(}(q_{0}^{\mathcal{D}},v_{0}),s\big{)}=(q^{\mathcal{D}},v)\big{]} \cdot\mathbb{P}(S_{0}\ldots S_{t-1}=s,C_{t}=c) \tag{3}\]0 (9) \[f_{t}\big{(}(q^{\mathcal{D}},c),v\big{)}=\sum_{s\in\Sigma^{t}}\big{[}\hat{ \delta}\big{(}(q_{0}^{\mathcal{D}},v_{0}),s\big{)}=(q^{\mathcal{D}},v)\big{]} \cdot\mathbb{P}(S_{0}\ldots S_{t-1}=s,C_{t}=c) \tag{3}\]1\[f_{t}\big{(}(q^{\mathcal{D}},c),v\big{)}=\sum_{s\in\Sigma^{t}}\big{[}\hat{ \delta}\big{(}(q_{0}^{\mathcal{D}},v_{0}),s\big{)}=(q^{\mathcal{D}},v)\big{]} \cdot\mathbb{P}(S_{0}\ldots S_{t-1}=s,C_{t}=c) \tag{3}\]2  
In the above derivation, step (4)\(\rightarrow\)(5) follows from (1). Step (5)\(\rightarrow\)(6) follows from the definitions of \(\theta_{q}\) and \(\mu_{q}\). Step (6)\(\rightarrow\)(7) uses the definitions of \(T\) and \(\mathcal{Q}\) in Lemma 3. Step (7)\(\rightarrow\)(8) uses the induction assumption. Step (8)\(\rightarrow\)(9) uses Lemma 1. The final step (9)\(\rightarrow\)(10) follows by combining the four Iverson brackets summed over \(q^{\prime\mathcal{D}}\) and \((v^{\prime},e)\) into a single Iverson bracket. To compute the table \(f_{n}\) containing \(f_{n}(q,v)\) for all \(q\in\mathcal{Q}\) and \(v\in\mathcal{V}\), we start with \(f_{0}\) and perform \(n\) update steps. The runtime bounds given in 2. and 3. can be verified by considering a \"push\" algorithm: When computing \(f_{t+1}\), we initialize the table with zeros and iterate over all \(q\in\mathcal{Q}\), \(v\in\mathcal{V}\) and \(q^{\prime}\in\{q^{\prime\prime}\in\mathcal{Q}:T(q,q^{\prime\prime})>0\}\); for each combination of \(q\), \(v\), and \(q^{\prime}\) with \(T(q,q^{\prime})>0\), we add \(f_{t}(q,v)\cdot T(q,q^{\prime})\) to \(f_{t+1}\big{(}q^{\prime},\theta_{q^{\prime}}(v,\eta_{q^{\prime}})\big{)}\). \(\Box\)  
As a direct consequence of the above lemma and of the DAA construction from Section 4, we arrive at our main theorem. **Theorem 2**: _Let a finite-memory text model \((\mathcal{C},c_{0},\Sigma,\varphi)\), a window-based pattern matching algorithm \(A\), a pattern \(p\) with \(|p|=m\), and the functions shift \({}^{A,p}\) and \(\xi^{A,p}\) be given. Then, the cost distribution \(\mathcal{L}(X_{n}^{A,p})\) can be computed using \(O(n^{2}\cdot m\cdot|\mathcal{Q}^{\mathcal{D}}|\cdot|\mathcal{C}|^{2}\cdot| \Sigma|)\) time and \(O(|\mathcal{Q}^{\mathcal{D}}|\cdot|\mathcal{C}|\cdot n\cdot m)\) space.