# Complete Subhedge Projection for Stepwise Hedge Automata +
## 3 Problem
### Basic Properties  
We first show that subhedge irrelevant prefixes remain irrelevant when extended by the nested word of any hedge. This property should be expected for any reasonable notion of subhedge irrelevance. **Lemma 1**. : _For any nested word prefix \(u\), language \(L,\mathbf{S}\subseteq\mathcal{H}_{\Sigma}\), and nested word \(v\in\mathcal{N}_{\Sigma}\), if the prefix \(u\) is subhedge irrelevant for \(L\) with schema \(\mathbf{S}\), then the prefix \(u\cdot v\) is so too._  
Proof. : Let \(u\) be subhedge irrelevant for \(L\) with schema \(\mathbf{S}\) and \(v\in\mathcal{N}_{\Sigma}\) a nested word. We fix arbitrary nested words \(v^{\prime},v^{\prime\prime}\in\mathcal{N}_{\Sigma}\) and a nested word suffix \(w\in\mathit{suffix}(N_{\Sigma})\) such that \(u\cdot v\cdot v^{\prime}\cdot w\in nw(\mathbf{S})\) and \(u\cdot v\cdot v^{\prime\prime}\cdot w\in nw(\mathbf{S})\). Since \(v\cdot v^{\prime}\) and \(v\cdot v^{\prime\prime}\) are also nested words, the subhedge irrelevance of \(u\) yields the following:  
\(u\cdot v\cdot v^{\prime}\cdot w\in nw(L)\Leftrightarrow u\cdot v\cdot v^{ \prime\prime}\cdot w\in nw(L)\). Hence, the nested word prefix \(u\cdot v\) is subhedge irrelevant for \(L\) with schema \(\mathbf{S}\). Definition 2: We call a binary relation \(D\) on prefixes of nested words a _difference relation on prefixes_ if for all prefixes of nested words \(u,u^{\prime}\in\text{prefs}(\mathcal{N}_{\Sigma})\) and nested words \(v\in\mathcal{N}_{\Sigma}\):  
\((u\cdot v,u^{\prime}\cdot v)\in D\Rightarrow(u,u^{\prime})\in D\). Lemma 2: \(\text{diff}_{\mathbf{S}}^{L}\) _is a difference relation._  
Proof: We must show for all prefixes \(u,u^{\prime}\in\text{prefs}(\mathcal{N}_{\Sigma})\) and nested words \(v\in\mathcal{N}_{\Sigma}\) that \((u\cdot v,u^{\prime}\cdot v)\in\text{diff}_{\mathbf{S}}^{L}\) implies \((u,u^{\prime})\in\text{diff}_{\mathbf{S}}^{L}\). So, let \(u,u^{\prime}\) be prefixes of nested words and \(v\) be a nested word such that \((u\cdot v,u^{\prime}\cdot v)\in\text{diff}_{\mathbf{S}}^{L}\). Then, there exists a nested suffix \(w\) such that  
\(u\cdot v\cdot w\in nw(L)\wedge u^{\prime}\cdot v\cdot w\in nw(\mathbf{S} \setminus L)\). The suffix \(\widetilde{w}=v\cdot w\) then satisfies \(u\cdot\widetilde{w}\in nw(L)\wedge u^{\prime}\cdot\widetilde{w}\in nw( \mathbf{S}\setminus L)\). Hence, \((u,u^{\prime})\in\text{diff}_{\mathbf{S}}^{L}\) as required. In the schema-free case of words, the complement \(\overline{\text{diff}_{\Sigma}^{L}}\) is an equivalence relation that is known as the Myhill-Nerode congruence. In the case of schemas, however, the complement \(\overline{\text{diff}_{\mathbf{S}}^{L}}\) may not be transitive; thus, it may not even be an equivalence relation. This might be surprising at first sight. Example 4: Let \(\Sigma=\{a,b\}\), \(L=\{\varepsilon,b,aa\}\) and \(\mathbf{S}=L\cup\{aab\}\). Then, \((\varepsilon,a)\in\overline{\text{diff}_{\mathbf{S}}^{L}}\) since there is no continuation that extends both \(\varepsilon\) and \(a\) into the schema. For the same reason, we have \((a,aa)\in\overline{\text{diff}_{\mathbf{S}}^{L}}\). However, \(\text{diff}_{\mathbf{S}}^{L}(\varepsilon,aa)\) since \(\varepsilon\cdot b\in L\) and \(aa\cdot b\in\mathbf{S}\setminus L\). Thus, \((\varepsilon,aa)\
ot\in\overline{\text{diff}_{\mathbf{S}}^{L}}\), so the complement \(\overline{\text{diff}_{\mathbf{S}}^{L}}\) is not transitive. It should be noted for all languages \(L\) that \(\overline{\text{diff}_{\mathcal{H}_{\Sigma}}^{L}}\) is reflexive and transitive, so it is an equivalence relation and thus a congruence. For general schemas \(\mathbf{S}\), \(\overline{\text{diff}_{\mathbf{S}}^{L}}\) may not be transitive, as shown by Example 4, and may thus not be congruent. This indicates that schemas may make it more difficult to decide subhedge irrelevance. Indeed, the natural manner in which one might expect to eliminate schemas based on complements does not work, as confirmed by following lemma (in particular, the counter-example in proof 1. # 2.