## 3 Deterministic Arithmetic Automata  
In this section, we introduce deterministic arithmetic automata (DAAs). They extend ordinary deterministic finite automata (DFAs) by performing a computation while one moves from state to state. Even though DAAs can be shown to be formally equivalent to families of DFAs on an appropriately defined larger state space, they are a useful concept before introducing probabilistic arithmetic automata (PAAs) and allow us to construct PAAs for the analysis of pattern matching algorithms in a simpler way. By using the PAA framework, we emphasize the connection between the problems discussed in the present article and those solved before using the same formalism: Other applications in biological sequence analysis include the exact computation of clump size distributions and _p_-values of sequence motifs [19], and the determination of seed sensitivity for pairwise sequence alignment algorithms based on filtering [20]. **Definition 1** (Deterministic Arithmetic Automaton, DAA): _A deterministic arithmetic automaton is a tuple_  
\[\mathcal{D}=\big{(}\mathcal{Q},q_{0},\Sigma,\delta,\mathcal{V},v_{0},\mathcal{ E},(\eta_{q})_{q\in\mathcal{Q}},(\theta_{q})_{q\in\mathcal{Q}}\big{)},\]  
_where \(\mathcal{Q}\) is a finite set of states, \(q_{0}\in\mathcal{Q}\) is the start state, \(\Sigma\) is a finite alphabet, \(\delta:\mathcal{Q}\times\Sigma\to\mathcal{Q}\) is a transition function, \(\mathcal{V}\) is a finite or countable set of values, \(v_{0}\in\mathcal{V}\) is called the start value, \(\mathcal{E}\) is a finite set of emissions, \(\eta_{q}\in\mathcal{E}\) is the emission associated to state \(q\), and \(\theta_{q}:\mathcal{V}\times\mathcal{E}\to\mathcal{V}\) is a binary operation associated to state \(q\)._  
Informally, a DAA starts with the state-value pair \((q_{0},v_{0})\) and reads a sequence of symbols from \(\Sigma\). Being in state \(q\) with value \(v\), upon reading \(\sigma\in\Sigma\), the DAA performs a state transition to \(q^{\prime}:=\delta(q,\sigma)\) and updates the value to \(v^{\prime}:=\theta_{q^{\prime}}(v,\eta_{q^{\prime}})\) using the operation and emission of the new state \(q^{\prime}\). Further, we define the associated joint transition function  
\[\hat{\delta}:(\mathcal{Q}\times\mathcal{V})\times\Sigma\to(\mathcal{Q}\times \mathcal{V}),\qquad\hat{\delta}\big{(}(q,v),\sigma\big{)}:=\big{(}\delta(q, \sigma)\,,\,\theta_{\delta(q,\sigma)}(v,\eta_{\delta(q,\sigma)})\big{)}.\]  
As usual, we extend the definition of \(\hat{\delta}\) inductively from \(\Sigma\) to \(\Sigma^{*}\) in its second argument by \(\hat{\delta}\big{(}(q,v),\varepsilon\big{)}:=(q,v)\) for the empty string \(\varepsilon\) and \(\hat{\delta}\big{(}(q,v),x\sigma\big{)}:=\delta\big{(}\hat{\delta}((q,v),x), \sigma\big{)}\) for all \(x\in\Sigma^{*}\) and \(\sigma\in\Sigma\). When \(\hat{\delta}\big{(}(q_{0},v_{0}),s\big{)}=(q,v)\) for some \(q\in\mathcal{Q}\) and \(s\in\Sigma^{*}\), we say that \(\mathcal{D}\) computes value \(v\) for input \(s\) and define \(\mathit{value}_{\mathcal{D}}(s):=v\). For each state \(q\), the emission \(\eta_{q}\) is fixed and could be dropped from the definition of DAAs. In fact, one could also dispense with values and operations entirely and define a DFA over state space \(\mathcal{Q}\times\mathcal{V}\), performing the same operations as a DAA. However, we intentionally include values, operations, and emissions to emphasize the connection to PAAs (which are defined in Section 5). As a simple example for a DAA, take a standard DFA \((\mathcal{Q},q_{0},\Sigma,\delta,F)\) with \(F\subset\mathcal{Q}\) being a set of final (or accepting) states. To obtain a DAA that counts how many times the DFA visits an accepting state when reading \(s\in\Sigma^{*}\), let \(\mathcal{E}:=\{0,1\}\) and define \(\eta_{q}:=1\) if \(q\in F\), and \(\eta_{q}:=0\) otherwise. Further define \(\mathcal{V}=\mathds{N}\) with \(v_{0}:=0\), and let the operation in each state be the usual addition: \(\theta_{q}(v,e):=v+e\) for all \(q\). Then \(\mathit{value}_{\mathcal{D}}(s)\) is the desired count.