# Efficient Construction of the Equation Automaton
## 5 Efficient Conversion Algorithm
### Computation of States
#### 5.1.2. \(\equiv_{e}\)-Equivalent States Merging  
Let us now turn to the computation of the set of states of the equation automaton. From Corollary 1, the c-continuation \(c_{x}(\mathrm{E})\) is a concatenation of distinct subexpressions of \(\mathrm{E}\), possibly reduced to a single subexpression or to \(1\). The following proposition shows that the c-continuation \(c_{x}(\mathrm{E})\) can be computed over the syntactic tree \(\mathrm{T}(\overline{\mathrm{E}})\) associated with the linearized version \(\overline{\mathrm{E}}\). **Proposition 5**. : _(Ref. [6]). Let \(\mathrm{E}\) be a regular expression and \(x\) a position in \(\mathrm{pos}(\mathrm{E})\). Let \(v_{x}\) be a node in \(\mathrm{T}(\overline{\mathrm{E}})\) such that \(\text{sym}(v_{x})=x\). The c-continuation \(c_{x}(\mathrm{E})\) is as follows:_  
\[c_{x}(\mathrm{E})=\underset{ \begin{subarray}{c}v_{x}\supseteq v\leq v_{ \overline{\mathrm{E}}}\\ f(v)\
eq\bot\end{subarray} }{\mathrm{\mathop{\mathrm{E}}}}F_{f(v)}\]  
_where \(\odot\) is the concatenation operator._  
_The function \(f\ :\ Nodes(\mathrm{E})\cup\{\bot\}\longrightarrow\ Nodes(\mathrm{E})\cup\{\bot\}\) is defined as follows:_  
\[f(v)=\left\{ \begin{array}{ll}\mathit{father}(v)&\text{if $\text{sym}( \mathit{father}(v))=*$ and $v\
eq v_{\overline{\mathrm{E}}}$}\\ \mathrm{right}(\mathit{father}(v))&\text{if $\text{sym}(\mathit{father}(v))= $.}\\ \bot&\text{otherwise.}\end{array} \right.\]  
_with \(\bot\) is an artificial node such that \(f(\bot)=\bot\)._  
Using Proposition 5, the computation of the set of states requires \(O(|\mathrm{E}\,|^{3})\) time and space complexity. This is due to the fact that the size of a c-continuation is in \(O(|\mathrm{E}\,|^{2})\). In order to reduce this complexity, we introduce a modified definition of pseudo-continuation introduced in [6] over an acyclic deterministic sub-automaton of the [PERSON] automaton, denoted by \(C_{=_{e}}(Id(\mathcal{T}_{\mathrm{E}}))\). When merging \(\equiv_{e}\)-equivalent states over \(Id(\mathcal{T}_{\mathrm{E}})\), we get the automaton \(C_{=_{e}}(Id(\mathcal{T}_{\mathrm{E}}))\). This step requires a linear time w.r.t the size of \(\mathrm{E}\) using [PERSON]'s algorithm [17], since the automaton \(Id(\mathcal{T}_{\mathrm{E}})\) is acyclic and deterministic. In the following, a state \((q,\mathrm{N}(q))\) in the automaton \(Id(\mathcal{T}_{\mathrm{E}})\) is called a _position state_, if there exists \(a\in A_{\mathrm{E}}\) and \((q^{\prime},\mathrm{N}(q^{\prime}))\in Q^{\prime}\) such that \(\delta^{\prime}((q^{\prime},N(q^{\prime})),a)=(q,N(q))\). The state \((0,N(0))\) is also considered as a _position state_. It is obvious to see that each _position state_ is associated with a unique position in \(\mathrm{pos}(\mathrm{E})\cup\{0\}\) and then it's can be associated with a c-continuation. Let \((q,N(q))\) and \((q^{\prime},N(q^{\prime}))\) two position states associated with the positions \(x\) and \(x^{\prime}\) in \(\text{pos}(\text{E})\). One can extend the \(\equiv_{\epsilon}\) relation over _position states_ in \(Id(\mathcal{T}_{\text{E}})\) as follows:  
\[(q,N(q))\equiv_{\epsilon}(q^{\prime},N(q^{\prime}))\Longleftrightarrow h(c_{x} (\text{E}))\equiv h(c_{x^{\prime}}(\text{E}))\]  
In the next, we will prove that the computation of the equivalence classes \(C_{\equiv_{\epsilon}}\) can be performed in a linear time w.r.t. the size of the regular expression over \(Id(\mathcal{T}_{\text{E}})\) using the notion of _pseudo-continuations_. For abbreviation, a state \((q,N(q))\) in \(Id(\mathcal{T}_{\text{E}})\) will be denoted by \(q\). We denote by \(\text{C}(q)\)_the pseudo-continuation_ associated with the _position state_\(q\) which is an implicit representation of its c-continuation \(c_{x}(\text{E})\), where \(x\) is the position letter of \(q\). We will show that the computation of the equivalence classes \(C_{\equiv_{\epsilon}}\) turns on the computation of _pseudo-continuation_\(C(q)\) over a particular \(\epsilon\)-transitions marking of the automaton \(Id(\mathcal{T}_{\text{E}})\).