# Complete Subhedge Projection for Stepwise Hedge Automata +
## 2 Preliminaries  
Let \(A\) and \(B\) be sets. If \(A\) is a subset of \(B\), then the complement of \(A\) in \(B\) is denoted by \(\overline{A}=B\setminus A\) while keeping the set relative to which the complement is taken implicit. The _domain_ of the binary relation \(r\subseteq A\times B\) is \(dom(r)=\{a\in A\mid\exists b\in B.\ (a,b)\in r\}\). A _partial function_\(f:A\hookrightarrow B\) is a binary relation \(f\subseteq A\times B\) that is functional. A _total function_\(f:A\to B\) is a partial function \(f:A\hookrightarrow B\) with \(dom(f)=A\). **Words**. Let \(\mathbb{N}\) be the set of natural numbers, including \(0\). Let the alphabet \(\Sigma\) be a set. The set of words over \(\Sigma\) is \(\Sigma^{*}=\cup_{n\in\mathbb{N}}\Sigma^{n}\). A word is \((a_{1},\ldots,a_{n})\in\Sigma^{n}\), where \(n\in\mathbb{N}\) is written as \(a_{1}\ldots a_{n}\). We denote the empty word of length \(0\) by \(\varepsilon\in\Sigma^{0}\), and by \(v_{1}\cdot v_{2}\in\Sigma^{*}\) the concatenation of two words \(v_{1},v_{2}\in\Sigma^{*}\). If \(v=u\cdot v^{\prime}\cdot w\) is a word, then we call \(u\) a prefix of \(v\) and \(v^{\prime}\) a factor of \(v\) and \(w\) a suffix of \(v\). Given any subset \(L\subseteq\Sigma^{*}\), we denote the set of prefixes of words in \(L\) by \(\mathit{prefs}(L)\) and the set of suffixes of words in \(L\) by \(\mathit{suffixs}(L)\). For any subalphabet \(\Sigma^{\prime}\subseteq\Sigma\), the projection of a word \(v\in\Sigma^{*}\) to \(\Sigma^{\prime}\) is the word \(\mathit{proj}_{\Sigma^{\prime}}(v)\) in \((\Sigma^{\prime})^{*}\) that is obtained from \(v\) by removing all letters from \(\Sigma\setminus\Sigma^{\prime}\). **Hedges**. Hedges are sequences of letters and trees \(\left\langle h\right\rangle\) with a hedge \(h\). More formally, a hedge \(h\in\mathcal{H}_{\Sigma}\) has the following abstract syntax:  
\[h,h^{\prime}\in\mathcal{H}_{\Sigma} := \varepsilon\quad|\quad a\quad|\quad\left\langle h\right\rangle \quad|\quad h\cdot h^{\prime}\qquad\text{ where }a\in\Sigma\]  
We assume \(\varepsilon\cdot h=h\cdot\varepsilon=h\) and \((h\cdot h_{1})\cdot h_{2}=h\cdot(h_{1}\cdot h_{2})\). Therefore, we consider any word in \(\Sigma^{*}\) as a hedge in \(\mathcal{H}_{\Sigma}\), i.e., \(\Sigma^{*}\
i aab=a\cdot a\cdot b\in\mathcal{H}_{\Sigma}\). Any hedge can be converted or stored as a graph. For the signature \(\Sigma=\left\{list,item,A,\ldots,Z\right\}\), the graph of an example hedge in \(\mathcal{H}_{\Sigma}\) is shown in Figure 1.  
It encodes the sequence of Xml documents in Figure 2:  
**Nested Words**. A nested word over \(\Sigma\) is a word over the alphabet \(\hat{\Sigma}=\Sigma\cup\left\{\left\langle,\right\rangle\right\}\) in which all parentheses are well-nested. Intuitively, this means that for any opening parenthesis, there is a matching closing parenthesis and vice versa. The set of nested words over \(\Sigma\) can be defined as the subsets of words over \(\hat{\Sigma}\) that are a linearization of the hedge, where the linearization function \(\mathit{nw}:\mathcal{H}_{\Sigma}\rightarrow(\Sigma\cup\left\{\left\langle, \right\rangle\right\})^{*}\) is defined as follows:  
\[\mathit{nw}(\varepsilon)=\varepsilon,\quad\mathit{nw}(\left\langle h\right\rangle )=\left\langle\cdot\mathit{nw}(h)\cdot\right\rangle,\quad\mathit{nw}(a)=a, \quad\mathit{nw}(h\cdot h^{\prime})=\mathit{nw}(h)\cdot\mathit{nw}(h^{\prime }).\]  
So, the set of all nested words over \(\Sigma\) is \(\mathit{nw}(\mathcal{H}_{\Sigma})\). Let \(\mathit{hdg}\) be the inverse of the injective function \(\mathit{nw}\) restricted to its image, so the mapping from nested words to hedges with \(\mathit{hdg}(\mathit{nw}(h))=h\) for all \(h\in\mathcal{H}_{\Sigma}\). **Nested Word Prefixes**. Prefixes, suffixes, and factors of nested words may not be nested words themselves. For instance, the hedge \(h=a\cdot\left\langle b\cdot c\right\rangle\) has the linearization \(\mathit{nw}(h)=a\left\langle bc\right\rangle\). Its prefix \(a\left\langle b\right\rangle\) is not well-nested since it has a dangling opening parenthesis.