# Complete Subhedge Projection for Stepwise Hedge Automata +
## 4 Hedge Automata
### Schema Completeness
This is why it is much better to assume only schema-completeness rather than full completeness for the input automata of safe-no-change projection. For congruence projection, schema-completeness will be assumed implicitly. We note that schema-completeness is well-defined even for nonregular schemas. For safe-no-change projection, we indeed do not have to restrict schemas to be regular, while for congruence projection, only regular schemas are considered. Furthermore, if \(A\) is schema-complete for the universal schema \(\mathbf{S}=\mathcal{H}_{\Sigma}\) and does not have inaccessible states, then \(A\) is complete. Schema-completeness of deterministic automata for regular schemas can always be made to hold as we will show next. For this we define that \(A\) is _compatible with schema_\(\mathsf{S}\) if for any hedge \(h\in\mathbf{S}\) there exists a run of \(A\) in \(run^{\Delta}(h)\). Schema-completeness implies compatibility, as shown by the next lemma. The converse is true only when assuming determinism. Lemma 5: _Let \(A\) be a deterministic Sha with schema \(\mathbf{S}\). Then, \(A\) is compatible with \(\mathsf{S}\) iff \(A\) is schema-complete for \(\mathbf{S}\)._  
Proof: Suppose that \(A\) is schema-complete for \(\mathbf{S}\) Wlog., we can assume \(\mathbf{S}\
eq\emptyset\). Note that if \(I=\emptyset\), then \(\varepsilon\) would be a blocking partial run for any hedge in \(\mathbf{S}\setminus\{\varepsilon\}\). Since \(\mathbf{S}\
eq\emptyset\), it follows that there exists \(q_{0}\in I\). So, \(q_{0}\) is a partial run for any hedge \(h\in\mathbf{S}\setminus\{\varepsilon\}\). Since there exist no blocking partial runs by schema-completeness, this run can be extended step by step to a run on any \(h\in\mathbf{S}\). Therefore, for any hedge \(h\in\mathbf{S}\), there exists some run by \(A\), showing compatibility. For the converse, let \(A\) be compatible with \(\mathbf{S}\) and deterministic. We have to show that \(A\) is schema-complete for \(\mathbf{S}\). Let \(v\) be a partial run of \(A\) on \(h\in\mathbf{S}\). By compatibility, there exists a run \(R\in run^{\Delta}(h)\) that starts in some initial state of \(A\). By determinism, \(v\) must be a prefix of \(nw(R)\). Thus, \(v\) is not blocking. Proposition 1: _Any Sha \(A\) with regular schema \(\mathbf{S}\) can be made schema-complete for \(\mathbf{S}\)._  
Proof: By Lemma 5, it is sufficient to make \(A\) compatible with \(\mathbf{S}\). Let \(B\) be a dSha with \(\mathbf{S}=\mathcal{L}(B)\). Automaton \(B\) is compatible with \(\mathbf{S}\). Since \(B\) is deterministic, Lemma 5 implies that \(B\) is schema-complete for \(\mathbf{S}\). Since \(\mathbf{S}\) is a schema for \(A\) with \(\mathcal{L}(A)\subseteq\mathcal{L}(B)\). We then compute the completion of \(compl(A)\). The product \(C=B\times compl(A)\) with final states \(FC=F^{B}\times F^{A}\) is schema-complete for schema \(\mathbf{S}\). Furthermore, since \(\mathcal{L}(A)\subseteq\mathbf{S}=\mathcal{L}(B)\), it follows that \(\mathcal{L}(C)=\mathcal{L}(B)\cap\mathcal{L}(A)=\mathcal{L}(A)\). Finally, note that the schema \(\mathbf{S}\) can be recognized by the same product \(C=B\times compl(A)\) except for replacing the set of final states \(F^{\mathbf{C}}\) by the set of schema final states \(F^{\mathbf{S}}=F^{B}\times(Q^{A}\cup\{sink\})\). We have \(\mathbf{S}=\mathcal{L}(C[F^{C}/F^{\mathbf{S}}])\), where \(C[F^{C}/F^{\mathbf{S}}]\) is the dSha obtained from \(C\) by replacing the set of final states \(F^{\mathbf{C}}\) with \(F^{\mathbf{S}}\).