# Complete Subhedge Projection for Stepwise Hedge Automata +
## 7 Congruence Projection
### Algorithm
#### 7.2.3 Updating the Difference Relation  
For any difference relation \(D\subseteq\mathcal{D}^{\Delta}\) and subset of states \(\mathcal{Q}\subseteq\mathcal{Q}\), we define a binary relation \(down^{\Delta}_{Q}(D)\subseteq\mathcal{Q}\times\mathcal{Q}\), such that for all states \(p_{1},p_{2}\in\mathcal{Q}\):  
\[(p_{1},p_{2})\in down^{\Delta}_{Q}(D)\text{ iff }\exists q_{1},q_{2}\in \mathcal{Q}.\ (q_{1}\oplus^{\Delta}p_{1},q_{2}\oplus^{\Delta}p_{2})\in D.\]  
For any subset of states \(\mathcal{Q}\subseteq\mathcal{Q}\) and difference relation \(D\in\mathcal{D}^{\Delta}\), let \(D_{\mathcal{Q}}\in\mathcal{D}^{\Delta}\) be the least difference relation that contains \(down^{\Delta}_{Q}(D)\):  
\[D_{\mathcal{Q}}=ldr^{\Delta}(down^{\Delta}_{Q}(D)).\]  
**Lemma 11**. : _The difference relation \(D_{\mathcal{Q}}\) can be computed in time \(O(|A|^{2})\) from \(\mathcal{Q}\), \(\Delta\), and \(D\)._  
Proof. : The binary relation \(down^{\Delta}_{Q}(D)\) can be computed in time \(O(|\Delta|^{2})\) from \(\mathcal{Q}\), \(D\), and \(\Delta\). The least difference relation \(ldr^{\Delta}(down^{\Delta}_{Q}(D))\) can be computed by ground datalog in time \(O(|A|^{2})\) from \(down^{\Delta}_{Q}(D)\) using Proposition 4. **Example 11**. : _Reconsider the dSha for the XPath filter \([\mathtt{self::list/child::item}]\) in Figure 4 with the set of schema-final states \(F_{\mathsf{S}}=\{4,5\}\). Since \(F=\{4\}\), we have \(F_{\mathsf{S}}\setminus F=\{5\}\). The initial difference relation is \(D0=D^{A,F_{\mathsf{S}}}_{init}\), which is the symmetric closure of \((\{0\}\times\{1,4,5\})\cup\{(1,4),(4,5)\}\). The subdge irrelevant states are \(Prj^{\Delta}(D0)=\{1,2,3,4,5\}\) since only state \(0\) can access two states in the difference relation \(D0\), the final state in \(F=\{4\}\), and a nonfinal state that is schema-final in \(F_{\mathsf{S}}\setminus F=\{5\}\) of some hedges. The difference relation \(down^{\Delta}_{\{0\}}(D^{A,F_{\mathsf{S}}}_{init})\) is the symmetric closure of \(\{1,2\}\times\{3\}\), which is equal to the difference relation \(D1=D0_{\{0\}}=ldr^{\Delta}(down^{\Delta}_{\{0\}}(D0))\). Hence, the projection states are \(Prj^{\Delta}(D1)=\{2,3,4,5\}\) since from states \(0\) and \(1\) one can still reach both \(1\) and \(3\) while \((1,3)\in D1\). The difference relation \(D2=down^{\Delta}_{\{1\}}(D1)\) is the symmetric closure of \(\{(1,2),(2,3)\}\). Hence, the projection states are \(Prj^{\Delta}(D2)=\{1,2,3,4,5\}\). From state \(1\), one can only reach states \(1\) and \(3\), which are not different for \(D2\)._  
Projection states for the initial difference relation contain all states that are safe for selection or safe for rejection with respect to the schema:  
**Lemma 12**. : _All states in safe\({}^{\Delta}(F)\) and safe\({}^{\Delta}(F_{\mathsf{S}}\setminus F)\) are subhedge irrelevant for \(D^{A,F_{\mathsf{S}}}_{init}\)._  
We omit the proof since the result is not used later on. Given a dSha \(A=(\Sigma,\mathcal{Q},\Delta,I,F)\) and a set \(F\subseteq F_{\textsf{S}}\subseteq\mathcal{Q}\), we now construct the congruence projection \(A^{\texttt{cgr}(\textsf{S})}\) as the following dSha\({}^{\perp}\):  
\[A^{\texttt{cgr}(\textsf{S})}=(\Sigma,\mathcal{Q}^{\texttt{cgr}},\Delta^{ \texttt{cgr}},I^{\texttt{cgr}(\textsf{S})},F^{\texttt{cgr}(\textsf{S})}),\]  
where the set of states, initial states, and final states are as follows:  
\[ \begin{array}{rcl}\mathcal{Q}^{\texttt{cgr}}&\subseteq&2^{\mathcal{Q}} \times\mathcal{D}^{\Delta}\\ I^{\texttt{cgr}(\textsf{S})}&=&\{(I,D^{A,F_{\textsf{S}}}_{init})\}\\ F^{\texttt{cgr}(\textsf{S})}&=&\left\{(Q,D^{A,F_{\textsf{S}}}_{init})\mid \left(\begin{array}{c}Q\
ot\in dPr\hat{\pi}^{\Delta}(D^{A,F_{\textsf{S}}}_{ init})\Rightarrow Q\cap F\
ot=\emptyset\quad\land\\ Q\in dPr\hat{\pi}^{\Delta}(D^{A,F_{\textsf{S}}}_{init})\Rightarrow acc^{ \Delta}(Q)\cap F\
ot=\emptyset\end{array}\right)\right\}\end{array}