# Efficient Construction of the Equation Automaton
## 5 Efficient Conversion Algorithm
### Computation of States
#### 5.1.2. \(\equiv_{e}\)-Equivalent States Merging
Definition 3: The pseudo-continuation \(\text{C}(q)\) associated with a position state \((q,\text{N}(q))\in Q^{\prime}\) in \(Id(\mathcal{T}_{\text{E}})\) is recursively defined by:  
\[\text{C}(q) = \left\{ \begin{array}{ll}\text{N}(q)&\text{if }\delta^{\prime}(q, \epsilon_{l+})=q^{\prime}\text{ and }\delta^{\prime}(q,\epsilon_{r+})=q^{\prime\prime},\\ \text{N}(q^{\prime})\cdot\text{C}(q^{\prime\prime})&\text{if }\delta^{\prime}(q, \epsilon_{1}^{*})=q^{\prime\prime}\text{ and }\delta^{\prime}(q^{\prime},a)=q\text{ for some }a\in A_{\text{E}},\\ \text{N}(q^{\prime})\cdot\text{C}(q^{\prime\prime})&\text{if }\delta^{\prime}(q, \epsilon_{1}^{*})=q^{\prime}\text{ and }\delta^{\prime}(q, \epsilon_{2}^{*})=q^{\prime\prime},\\ a\cdot\text{C}(q^{\prime})&\text{if }\delta^{\prime}(q,a)=q^{\prime},\text{ for all }a\in A_{\text{E}},\\ \text{C}(q^{\prime})&\text{if }\delta^{\prime}(q,\epsilon)=q^{\prime}.\end{array} \right. \tag{5}\]  
In order to compute efficiently the set of pseudo-continuations associated with the position states in \(Id(\mathcal{T}_{\text{E}})\), we define an acyclic deterministic sub-automaton \(C_{\equiv_{\epsilon}}(Id(\mathcal{T}_{\text{E}}))=\langle Q_{\equiv_{ \epsilon}},A_{\text{E}},I,\delta^{\prime\prime},F\rangle\) of the Thompson automaton as follows:  
* \(A=\{\epsilon_{0},\cdots,\epsilon_{\mid\text{Exp}\mid}\}\cup A_{\text{E}}\). * \(Q_{\equiv_{\epsilon}}=\{(q,\text{C}(q))|\;(q,\text{N}(q))\in Q^{\prime}\}\), i.e., a state in \(Id(\mathcal{T}_{\text{E}})\) is replaced by \((q,C(q))\). * The transition function \(\delta^{\prime\prime}\) is defined as follows:  
Let us define the equivalence relation \(\approx\) over the _position states_ of \(C_{\equiv_{\epsilon}}(Id(\mathcal{T}_{\text{E}}))\) as follows:  
\[(q,\text{C}(q))\approx(q^{\prime},\text{C}(q^{\prime}))\Leftrightarrow\text{ C}(q)\equiv\text{C}(q^{\prime}) \tag{6}\]  
Thus we have:  
\[[q]_{\approx}=[q^{\prime}]_{\approx}\Leftrightarrow\text{C}(q)\equiv\text{C}( q^{\prime}) \tag{7}\]  
Let \(\overline{h}\) be the application that maps a letter \(\epsilon_{i}\) to the letter \(i\). By construction, the following proposition holds. **Proposition 6**. : _Let \((q,\mathrm{C}(q))\) be a position state in \(C_{\equiv_{e}}(Id(\mathcal{T}_{\mathrm{E}}))\). We have:_  
\[\overline{h}(\overset{\rightarrow}{L}_{q}(C_{\equiv_{e}}(Id(\mathcal{T}_{ \mathrm{E}}))))=C(q)\]  
**Example 6**. : _Let us consider the Thompson automaton \(\mathcal{T}_{\mathrm{E}}\) defined in previous examples. Figure 7 schematizes the derived automaton from \(Id(\mathcal{T}_{\mathrm{E}})\) after pseudo continuations computation for position states._  
_Notice that dotted \(\epsilon\)-transitions are temporarily disabled and dashed ones are temporarily added._  
_The position states in the automaton \(Id(\mathcal{T}_{\mathrm{E}})\) are \(\{0,5,8,11,16\}\). According to the definition of a pseudo continuation (see Formula (7)), the pseudo-continuations associated with position states are computed over the automaton \(Id(\mathcal{T}_{\mathrm{E}})\) as follows:_  
\[ \begin{array}{l}C(5)=C(8)=C(11)=10\cdot 1\\ C(16)=15\cdot 1\end{array} \]  
_On the other hand, we have:_  
\[ \begin{array}{l}\overset{\rightarrow}{L}_{5}(C_{\equiv_{e}}(Id(\mathcal{T} _{\mathrm{E}})))=\overset{\rightarrow}{L}_{8}(C_{\equiv_{e}}(Id(\mathcal{T} _{\mathrm{E}})))=\overset{\rightarrow}{L}_{11}(C_{\equiv_{e}}(Id(\mathcal{T} _{\mathrm{E}})))=\epsilon_{10}\cdot\epsilon_{1}\\ \overset{\rightarrow}{L}_{16}(C_{\equiv_{e}}(Id(\mathcal{T}_{\mathrm{E}})))= \epsilon_{15}\cdot\epsilon_{1}\end{array} \]  
The following proposition is fundamental to prove that the equivalence relation \(\equiv_{e}\) using the notion of c-continuation is the same when using pseudo-continuations \(\mathrm{C}(q)\). **Proposition 7**. : _Let \(q\) (resp. \(q^{\prime}\)) be a position state associated with a position \(x\in\mathrm{pos}(\mathrm{E})\) (resp. \(x^{\prime}\in\mathrm{pos}(\mathrm{E})\)) in \(C_{\equiv_{e}}(Id(\mathcal{T}_{\mathrm{E}}))\).