# Complete Subhedge Projection for Stepwise Hedge Automata +
## 8 Earliest Membership with Subhedge Projection
### Adding Subhedge Projection  
We now enhance any earliest membership for dShas with subhedge projection. The idea is to combine subhedge projection with earliest membership. So, suppose that we are given a schema \(\mathbf{S}\) and two automata, \(A^{\pi}\) and \(A_{e}\), with schema \(\mathbf{S}\) that recognize the same language up to the schema, so \(\mathcal{L}(A^{\pi})\cap\mathcal{L}(\mathbf{S})=\mathcal{L}(A_{e})\cap \mathcal{L}(\mathbf{S})\). Furthermore, assume that \(A_{e}\) has a selection state \(sel\), indicating certain membership at the earliest possible prefix.  
In order to obtain the earliest membership with subhedge projection, we combine the two shA\({}^{\downarrow}\)s into a single shA\({}^{\downarrow}\), \(A^{\pi}_{e}=(\sum_{e}Q^{\pi}_{e}\), \(\Delta^{\pi}_{e}\), \(I^{\pi}_{e}\), \(F^{\pi}_{e}\)), basically running both automata in parallel but under shared control. The state set of \(A^{\pi}_{e}\) are as follows:  
\[\begin{array}{l}Q^{\pi}_{e}=(Q^{\pi}\times(Q_{e}\setminus\{sel\}))\cup\{sel\} \\ I^{\pi}_{e}=(I^{\pi}\times(I_{e}\setminus\{sel\}))\cup\{sel\mid sel\in I_{e} \}\\ F^{\pi}_{e}=(F^{\pi}\times(F_{e}\setminus\{sel\}))\cup\{sel\}\end{array}\]  
The transition rules in \(\Delta^{\pi}_{e}\) are given in Figure 20. Any run of \(A^{\pi}_{e}\) synchronizes parallel runs of \(A^{\pi}\) and \(A_{e}\) as follows: whenever \(A_{e}\) goes to \(sel\), then \(A^{\pi}_{e}\) does so too, and whenever \(A^{\pi}\) goes into a subhedge projection state, then it makes \(A_{e}\) jump over the subsequent subhedge.  
For illustration, we reconsider the dSha from Figure 4. The earliest dSha\({}^{\downarrow}\) with subhedge projection \(A^{\textit{src}}_{e(\mathbf{S})}\) is given in Figure 21. Here, we combine the safe-no-change projection \(A^{\textit{src}}\) from Figure 11 with the earliest membership tester \(A_{e(\mathbf{S})}\) from Figure 19. Their combination \(A^{\textit{src}}_{e(\mathbf{S})}\) represents the pattern \([\texttt{self:list/child:item}]\) with schema \([\texttt{doc}]\) in a concise manner. After prefix \(\langle\texttt{list(item}\), it detects certain membership: for the prefix \(\langle\texttt{list(list}\), it detects that the subhedge is irrelevant, and after prefix \(\langle\texttt{item}\), it detects certain nonmembership.  
input hedge, while skipping subhedges starting in subhedge projection states of \(A^{\pi}\). These include the subhedges starting in a projection state when evaluating \(A_{c}^{\pi}\) on \(h\). Applying Proposition 2 to \(A^{\pi}\), such subhedges are irrelevant for \(\mathcal{L}(A^{\pi})\) with respect to \(\mathbf{S}\), since \(A^{\pi}\) is assumed to be deterministic. Since \(\mathcal{L}(A^{\pi})\cap\mathbf{S}=\mathcal{L}(A_{e})\cap\mathbf{S}\), skipping such a subhedge does not affect acceptance by \(A_{e}\) for hedges inside schema \(\mathbf{S}\). Therefore, the evaluator of \(A_{e}^{\pi}\) is earliest with respect to \(\mathbf{S}\), too.  
The above proposition shows that if \(A^{\pi}\) is complete for subhedge projection, then \(A_{e}^{\pi}\) is also complete for subhedge projection while also being earliest.  
Theorem 4: _For any complete \(d\textsc{Gha}\)A with schema \(\mathbf{S}\), the \(d\textsc{Gha}\)A\({}^{cqgr}(\mathbf{S})_{e(\mathbf{S})}\) is earliest and complete for subhedge projection for schema \(\mathbf{S}\)._  
Proof: The congruence projection \(A^{cqgr}(\mathbf{S})\) is sound by Proposition 2 and complete for subhedge projection wrt \(\mathbf{S}\) by Theorem 3. The automaton \(A_{e(\mathbf{S})}\) discussed in Section 8.1 is earliest for \(\mathbf{S}\). So, their combination \(A^{cqgr}(\mathbf{S})_{e(\mathbf{S})}\) yields the earliest automaton with complete subhedge projection wrt \(\mathbf{S}\) using Proposition 7.