# Complete Subhedge Projection for Stepwise Hedge Automata +
## 3 Problem
### Hedge Pattern Matching  
We are interested in algorithms that match a hedge pattern against a hedge. We start with algorithms that test whether such matching exists. This is sometimes called filtering or, alternatively, Boolean query answering. In Section 10, we consider the more general problem of returning the set of matchings. This problem is sometimes called monadic query answering. Our experiments in Section 11 apply monadic query answering for regular XPath queries. We start from hedge patterns that are nested regular expressions with letters in the signature \(\Sigma\). For these, we fix a set \(V\) of recursion variables and assume that it is disjointed from \(\Sigma\). \[e,e^{\prime}\in nRegExp_{\Sigma}:=\ \varepsilon\ |\ a\ |\ z\ |\ e\cdot e^{\prime}\ |\ e+e^{\prime}\ |\ e^{*}\ |\ \langle e\rangle\ |\ \mu z.e\qquad\text{where }a \in\Sigma,\ z\in V\]  
Each nested regular expression \(e\in nRegExp_{\Sigma}\) is satisfied by a subset of hedges in \([\![e]\! ]\in\mathcal{H}_{\Sigma\cup V}\). We recall the definition of this set only informally. The expression \(\varepsilon\) is satisfied only by the empty word, expression \(a\in\Sigma\) only by the hedge \(a\) only, and expression \(z\in V\) only by the one letter hedge \(z\). An expression \(e\cdot e^{\prime}\) with the concatenation operator and \(e,e^{\prime}\in nRegExp_{\Sigma}\) is satisfied by the concatenations of hedges satisfying \(e\) and \(e^{\prime}\), respectively. An expression \(e^{*}\) with Kleene's star operator and \(e\in nRegExp_{\Sigma}\) is satisfied by repetitions of words satisfying \(e\). The Kleene star provides for horizontal recursion on hedges. The \(\mu\) expression \(\mu z.e\), where \(z\in V\) and \(e\in nRegExp_{\Sigma}\), is satisfied by all hedges without recursion variable \(x\) in which \(z\) is repeatedly replaced by a hedge satisfying \(e\) until it disappears. We adopt the usual restriction [28] that in any nested regular expression \(\mu z.e\), all occurrences of \(z\) in \(e\) are guarded by a tree constructor \(\langle.\rangle\). In this way, the \(\mu\)-operator provides proper vertical recursion. Also note that, for defining sublanguages of \(\mathcal{H}_{\Sigma}\), we only need such expressions in \(nRegExp_{\Sigma}\) in which all occurrences of recursion variables \(z\) are bound in the scope of binder \(\mu z\). It is well known that nested regular expressions in \(nRegExp_{\Sigma}\) can define all regular sublanguages of hedges in \(\mathcal{H}_{\Sigma}\), i.e., they have the same expressiveness as hedge automata with alphabet \(\Sigma\). Analogous results for regular tree expressions and tree automata are folklore [29]. **Example 1** (Nested regular expressions of regular XPath filters). : _For instance, we can define subsets of hedge encodings of XML documents with two kinds of elements in \(\Sigma=\{\texttt{list},\texttt{item}\}\) by expressions in \(n\texttt{RegExp}_{\Sigma}\). For this article, we will use an encoding of the XML document, which produces hedges that satisfy the following regular expression \(\texttt{doc}\in n\texttt{RegExp}_{\Sigma}\), where \(z\in V\):_  
\[\texttt{doc}=_{\texttt{def}}\texttt{tree}^{*}\quad\text{ where }\quad\text{tree}=_{ \texttt{def}}\mu z.\ \big{(}(\texttt{list}+\texttt{item})\cdot z^{*}\big{)}\]  
_In our application, the encodings are a little richer in order to distinguish different types of XML nodes such as elements, attributes, comments, and texts. An XPath filter such as [self::list/child::item] can then be expressed by the nested regular expression:_  
\[\text{filter}=_{\texttt{def}}\big{\langle}\texttt{list}\cdot\texttt{doc}\cdot \langle\texttt{item}\cdot\texttt{doc}\rangle\cdot\texttt{doc}\]  
General compilers from regular downward XPath filter queries to nested regular expressions were proposed in [8]. An implementation was developed in the context of the AStream tool [21]. We will use schemas \(S\subseteq\mathcal{H}_{\Sigma}\) to restrict the inputs of our pattern-matching problem.