# Efficient Construction of the Equation Automaton
## 3 Equation Automaton
### C-Continuation Automaton  
This automaton has been introduced by [PERSON] and [PERSON] [6] to efficiently compute the equation automaton. Let us recall the notion of c-derivative, c-continuation and c-continuation automaton. Definition 1: (c-derivative with respect to a letter). The c-derivative of a regular expression \(\mathrm{E}\) with respect to a letter \(a\) is the regular expression \(d_{a}(\mathrm{E})\) defined by:  
\[d_{a}(0) = d_{a}(1)=0,\] \[d_{a}(x) = \text{{if }}a=x\text{{then }}1\text{{else }}0,\] \[d_{a}(\mathrm{F}+\mathrm{G}) = \text{{if }}d_{a}(\mathrm{F})\
eq 0\text{{then }}d_{a}(\mathrm{F}) \text{{else }}d_{a}(\mathrm{G}),\] \[d_{a}(\mathrm{F}\cdot\mathrm{G}) = \text{{if }}d_{a}(\mathrm{F})\
eq 0\text{{then }}d_{a}(\mathrm{F}) \cdot\mathrm{G}\text{{else }}\lambda(\mathrm{F})\cdot d_{a}(\mathrm{G}),\] \[d_{a}(\mathrm{F}^{*}) = d_{a}(\mathrm{F})\cdot\mathrm{F}^{*}\,.\]  
The c-derivative with respect to a word \(u=u_{1}\cdots u_{n}\) is defined recursively by the rules: \(d_{\varepsilon}(\mathrm{E})=\mathrm{E}\) and \(d_{u_{1}\cdots u_{n}}(\mathrm{E})=d_{u_{2}\cdots u_{n}}(d_{u_{1}}(\mathrm{E}))\). Theorem 2. (Theorem 4 in [6]). : Let \(\mathrm{E}\) be a linear regular expression and a be a letter from \(\mathrm{E}\). Then all non-zero c-derivatives of the form \(d_{ua}(\mathrm{E})\), where \(u\) is an arbitrary word, are equal. Theorem 2 allows us to define the c-continuation \(c_{a}(\mathrm{E})\) of \(a\) in a linear expression \(\mathrm{E}\) as the unique value of the non-zero c-derivatives \(d_{ua}(\mathrm{E})\). Proposition 1: (Proposition 6 in [6]). : _For every letter \(a\) of a linear expression \(\mathrm{E}\), the c-continuation \(c_{a}(\mathrm{E})\) is such that:_  
\[c_{a}(a) = 1,\] \[c_{a}(\mathrm{F}+\mathrm{G}) = \text{{if }}c_{a}(\mathrm{F})\text{{exists }}\text{{then }}c_{a}(\mathrm{F})\text{{else }}c_{a}(\mathrm{G}),\] \[c_{a}(\mathrm{F}\cdot\mathrm{G}) = \text{{if }}c_{a}(\mathrm{F})\text{{exists }}\text{{then }}c_{a}(\mathrm{F})\cdot\mathrm{G}\text{{else }}c_{a}(\mathrm{G}),\] \[c_{a}(\mathrm{F}^{*}) = c_{a}(\mathrm{F})\cdot\mathrm{F}^{*}\,.\]  
Corollary 1: (Corollary 5 in [6]). : _For every letter \(a\) of a linear expression \(\mathrm{E}\), the c-continuation \(c_{a}(\mathrm{E})\) is either \(1\) or a subexpression of \(\mathrm{E}\) or a product of subexpressions._  
More precisely, for a linear regular expression \(\mathrm{E}\), we have \(c_{a}(\mathrm{E})=H_{0}\cdots H_{k}\), where \(H_{i}\) is a subexpression of \(\mathrm{E}\), for all \(0\leq i\leq k\). We now consider a regular expression \(\mathrm{E}\) over \(A\). Let \(\overline{\mathrm{E}}\) be the linearized form of \(\mathrm{E}\) over \(\mathrm{pos}(\mathrm{E})\) and \(h\) be the mapping from \(\mathrm{pos}(\mathrm{E})\) onto \(A_{\overline{\mathrm{E}}}\). In order to simplify the writing for a regular expression \(\mathrm{E}\), we consider by convention that \(c_{0}(\mathrm{E})=d_{\varepsilon}(\overline{\mathrm{E}})=\overline{\mathrm{E}}\) and \(c_{x}(\mathrm{E})\) will denote \(c_{x}(\overline{\mathrm{E}})\). Figure 3: The equation automaton \(\mathcal{E}_{\mathrm{E}}\). **Definition 2**. : _(\(c\)-continuation automaton) The \(c\)-continuation automaton of \(\mathrm{E}\), \(\mathcal{C}_{\mathrm{E}}=\langle Q,A_{\mathrm{E}},i,\delta,\)\(F\rangle\), is defined by:_  
* \(\mathrm{Q}=\{(x,c_{x}(\mathrm{E}))\mid x\in\mathrm{pos}(\mathrm{E})\cup\{0\}\}\)_,_
* \(i=(0,c_{0}(\mathrm{E}))\)_,_
* \(F=\{(x,c_{x}(\mathrm{E}))\mid\lambda(c_{x}(\mathrm{E}))=1\}\)_,_
* \(\delta((x,c_{x}(\mathrm{E})),a)=\{(y,c_{y}(\mathrm{E})\mid h(y)=a\text{ and }d_{y}(c_{x}(\mathrm{E}))\equiv c_{y}(\mathrm{E})\},\forall x\in \mathrm{pos}(\mathrm{E})\cup\{0\}\) _and_ \(\forall a\in A_{\mathrm{E}}\)_._  
We note that the number of states of \(\mathcal{C}_{\mathrm{E}}\) is exactly \(||\,\mathrm{E}\,||+1\). **Corollary 2**. : _(Corollary 7 in [6]). Let \(\mathrm{E}\) be a regular expression. One has: \(\mathrm{L}(\mathcal{C}_{\mathrm{E}})=\mathrm{L}(\mathrm{E})\)._  
**Example 3**.