## 5 Probabilistic Arithmetic Automata
### Constructing a PAA from a DAA and a Text Model  
We now formally state how to combine a DAA and a text model into a PAA that allows us to compute the distribution of values produced by the DAA when processing a random text. **Definition 5** (PAA induced by DAA and text model): _Let a text model \(M=(\mathcal{C},c_{0},\Sigma,\varphi)\) and a DAA \(\mathcal{D}=\big{(}\mathcal{Q}^{\mathcal{D}},q_{0}^{\mathcal{D}},\Sigma, \delta,\mathcal{V},v_{0},\mathcal{E},(\eta_{q})_{q\in\mathcal{Q}^{\mathcal{D} }},(\theta_{q}^{\mathcal{D}})_{q\in\mathcal{Q}^{\mathcal{D}}}\big{)}\) over the same alphabet \(\Sigma\) be given. Then, we define the PAA induced by \(\mathcal{D}\) and \(M\) by giving_  
* _a state space_ \(\mathcal{Q}:=\mathcal{Q}^{\mathcal{D}}\times\mathcal{C}\)_,_
* _a start state_ \(q_{0}:=(q_{0}^{\mathcal{D}},c_{0})\)_,_
* _transition probabilities_ \[T\big{(}(q,c),(q^{\prime},c^{\prime})\big{)}:=\sum_{\sigma\in\Sigma:\,\delta( q,\sigma)=q^{\prime}}\varphi(c,\sigma,c^{\prime}),\] (2)
* _(deterministic) emission probability vectors_ \(\mu_{(q,c)}(e):=\llbracket e=\eta_{q}\rrbracket\) _for all_ \((q,c)\in\mathcal{Q}\)_,_
* _operations_ \(\theta_{(q,c)}(v,e):=\theta_{q}^{\mathcal{D}}(v,e)\) _for all_ \((q,c)\in\mathcal{Q}\)Note that states having zero probability of being reached from \(q_{0}\) may be omitted from \(\mathcal{Q}\) and \(T\) without changing the PAA's state, emission or value process. The next lemma states that the PAA given by Definition 3 indeed reflects the probabilistic behavior of the input DAA acting on a random text generated by the text model. Furthermore, it gives the runtime required to compute the distribution of DAA values via dynamic programming. **Lemma 3** (Properties of PAA induced by DAA and text model): _Let a text model \(M=(\mathcal{C},c_{0},\Sigma,\varphi)\) and a DAA \(\mathcal{D}=\big{(}\mathcal{Q}^{\mathcal{D}},q_{0}^{\mathcal{D}},\Sigma, \delta,\mathcal{V},v_{0},\mathcal{E},(\eta_{q})_{q\in\mathcal{Q}^{\mathcal{D} }},(\theta_{q}^{\mathcal{D}})_{q\in\mathcal{Q}^{\mathcal{D}}}\big{)}\) be given and let \(\mathcal{P}=\big{(}\mathcal{Q},q_{0},T,\mathcal{V},v_{0},\mathcal{E},\mu=(\mu_ {q})_{q\in\mathcal{Q}},\theta=(\theta_{q})_{q\in\mathcal{Q}}\big{)}\) be the PAA given by Definition 5. Then,_  
1. \(\mathcal{L}(V_{t})=\mathcal{L}\big{(}\text{value}_{\mathcal{D}}(S_{0}\ldots S _{t-1})\big{)}\) _for all_ \(t\in\mathbb{N}_{0}\)_, where_ \(S\) _is a random text according to the text model_ \(M\)_,_
2. _the value distribution_ \(\mathcal{L}(V_{n})\) _can be computed with_ \(O(n\cdot|\mathcal{Q}^{\mathcal{D}}|\cdot|\mathcal{C}|^{2}\cdot|\Sigma|\cdot \vartheta_{n})\) _operations using_ \(O(|\mathcal{Q}^{\mathcal{D}}|\cdot|\mathcal{C}|\cdot\vartheta_{n})\) _space, and_
3. _if for all_ \(c\in\mathcal{C}\) _and_ \(\sigma\in\Sigma\)_, there exists at most one_ \(c^{\prime}\in\mathcal{C}\) _such that_ \(\varphi(c,\sigma,c^{\prime})>0\)_, then the runtime is bounded by_ \(O(n\cdot|\mathcal{Q}^{\mathcal{D}}|\cdot|\mathcal{C}|\cdot|\Sigma|\cdot \vartheta_{n})\)_._  
ProofAs in Section 5.2, we define \(f_{t}(q,v):=\mathbb{P}(Q_{t}=q,V_{t}=v)\). To prove 1, we show that  
\[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}\]  
for all \(q^{\mathcal{D}}\in\mathcal{Q}^{\mathcal{D}}\), \(c\in\mathcal{C}\), \(v\in\mathcal{V}\), and \(t\in\mathbb{N}_{0}\). For \(t=0\), Equation (3) is satisfied by definitions of PAAs, DAAs and text models. For \(t>0\) we prove it inductively. Assume Equation (3) to be correct for all \(t^{\prime}\) with \(0\leq t^{\prime}<t\).