# Complete Subhedge Projection for Stepwise Hedge Automata +
## 4 Hedge Automata
### Schema Completeness  
Schemas are inputs of the membership problem that we consider while completeness is a fundamental property of automata. To combine both aspects appropriately, we propose the notion of schema completeness, which we define uniformly for both Sha and Sha\({}^{\downarrow}\)s.  
We call a set of \(\Delta\) transition rules Sha\({}^{\downarrow}\) complete if all its relations \((a^{\Delta})_{a\in\Sigma}\), \(\langle\rangle^{\Delta}\), and @\({}^{\Delta}\) are total. For Sha, we require that \(\langle\rangle^{\Delta}\) is a nonempty set (instead of a total relation). A Sha or Sha\({}^{\downarrow}\)\(A\) is called complete if \(\Delta\) is complete and \(I\
eq\emptyset\). We can complete any Sha or Sha\({}^{\downarrow}\) by adding a fresh sink state and also transition rules into the sink state for all left-hand sides, for which no other transition rule exists. The sink state is made initial if and only if there is no initial state before. It is not final though. We denote the completion of \(A\) by \(compl(A)\). **Definition 5**. : _A partial run of \(A\) on a hedge \(h\) is a prefix \(r\) of a run of \(compl(A)\) on \(h\), such that_  
* \(r\) _ends with some state of_ \(\mathcal{Q}\)_, and_
* \(r\) _does not contain the sink state of_ \(compl(A)\)_._  
_A partial run \(r\) of \(A\) on \(h\) is called blocking if there does not exist any partial run \(r^{\prime}\) of \(A\) on \(h\), such that \(r\) is a strict prefix of \(r^{\prime}\)._  
For instance, consider the hedge \(h=\langle\texttt{list}\cdot\langle\texttt{item}\rangle\rangle\). The dSha in Figure 4 has the unique run \(R=0\cdot\langle\cdot 0\cdot\texttt{list}\cdot 1\cdot\langle\cdot 0\cdot \texttt{item}\cdot 2\rangle\cdot 3\cdot\rangle\cdot 4\) on \(h\) that is illustrated in Figure 5. The partial runs of \(h\) are thus all prefixes of \(nw(R)\) that end with some state, i.e., \(0\cdot\langle\cdot 0\), \(0\cdot\langle\cdot 0\cdot\texttt{list}\cdot 1\), etc. None of these partial runs are blocking. **Definition 6**. : _A schema for an automaton \(A\) is a hedge language \(\mathcal{S}\subseteq\mathcal{H}_{\Sigma}\), such that \(\mathcal{L}(A)\subseteq\mathcal{S}\). We call the automaton \(A\) schema-complete for schema \(\mathcal{S}\) if no hedge \(h\in\mathcal{S}\) has a blocking partial run of \(A\)._  
Schemas \(\mathcal{S}\) are usually used to restrict the type of hedges that a problem may accept as input. The dSha pattern-matching problem for a schema \(\mathcal{S}\) takes two inputs: a hedge \(h\in\mathcal{S}\) and an automaton \(A\), rather than a nested regular expression \(e\). The automaton \(A\) then selects those input hedges \(h\in\mathcal{S}\) that match the pattern, i.e., such that \(h\in\mathcal{L}(A)\). For this reason, we assume that \(\mathcal{S}\) is a schema for \(A\), i.e., \(\mathcal{L}(A)\subseteq\mathcal{S}\). We will often assume that \(A\) is schema-complete for \(\mathcal{S}\), so that no partial run of \(A\) on any input hedge \(h\in\mathcal{S}\) may ever block. This can always be achieved next based on the next Lemma 5. **Example 5**. : _The dSha in Figure 4 for the XPath filter \([\texttt{self:list}/\texttt{child:item}]\) has signature \(\Sigma=\{\texttt{item},\texttt{list}\}\). It is schema-complete for schema \([\texttt{doc}]\). To make this happen, we added state \(5\) to this automaton, which is not used by any successful run. Still, this Sha is not complete. For completing it, we would have to run \(5\) into sink states by adding many transitions into it, such as \(0@4\to 5\) and \(0@5\to 5\), and also add for all other states \(q\in\{1,2,3,4,5\}\) the transition rules \(q\xrightarrow{\texttt{list}}5\), \(q\xrightarrow{\texttt{item}}5\), \(q@4\to 5\), and \(q@5\to 5\)._  
As we will see, automaton completion would make the safe-no-change algorithm incomplete for subhedge projection for Example 5. Without schema-completeness, however, safe-no-change projection may be unsound: it might overlook the rejection of hedges inside the schema.