# Complete Subhedge Projection for Stepwise Hedge Automata +
## 1 Introduction
In particular, it was recently demonstrated that the earliest query answering for regular monadic queries defined by deterministic Shas[21] has a lower worst-case complexity than for deterministic Nwas[22]. Thereby, the earliest query answering for regular queries became feasible in practice for the first time. On the other hand side, it is still slower experimentally than the best existing non-earliest approaches for general regular monadic queries on Xml streams (see [23] for a comparison) since the latter supports projection. How projections could be made for Shas has not been studied before the conference version of the present article [24]. Consider the example of the XPath filter [self::list/child::item] that is satisfied by an Xml document if its root is a list element that has an item child. With the encoding of the Xml document as hedges are chosen in the present article, satisfying hedges have the form \(\left\langle\texttt{list}\cdot h_{1}\cdot\left\langle\texttt{item}\cdot h_{2 }\right\rangle\cdot h_{3}\right\rangle\cdot h_{4}\), and for some hedges, \(h_{1},h_{2},h_{3},h_{4}\). When evaluating this filter on a hedge, it is sufficient to inspect the first subtree for having the root label list and then all its children until one with a root label item is found. The subhedges of these children, i.e., the hedge \(h_{3}\) and the subhedges of the top-level trees in \(h_{1}\) and \(h_{3}\), can be projected away, as well as the hedge \(h_{4}\): they do not have to be inspected for evaluating this filter. However, one must memorize whether the level of the current node is 0, 1, or greater. This level of information can be naturally updated in a top-down manner. The evaluators of Shas, however, operate bottom-up and left-to-right exclusively. Therefore, projecting evaluators for Shas need to be based on more general machines. We propose _downward stepwise hedge automata_ (Sha\({}^{\downarrow}\)s), a variant of Shas that supports top-down processing. They are basically Neumann and Seidl's pushdown forest automata [25], except that they are applied to unlabeled hedges instead of labeled forests. Furthermore, Nwas are known to operate in basically the same manner on nested words [26] while allowing for slightly more general visible pushdowns. We then distinguish subhedge projection states for Sha\({}^{\downarrow}\)s, and show how to use them to evaluate Shas with subhedge projection both in memory and in streaming mode. As a first contribution, we present the safe-no-change compiler from Shas to Sha\({}^{\downarrow}\)s that can distinguish appropriate subhedge projection states. The idea is that the safe-no-change Sha\({}^{\downarrow}\) can distinguish contexts in which the states of the Sha will safely not change. For instance, the XPath filter [self::list/child::item] can be defined by a deterministic Sha operating bottom-up which our compiler maps to the Sha\({}^{\downarrow}\) operating top-down. The context information made explicit by top-down processing is about the levels of the states. This permits us to distinguish projection states starting from level 2, and in which subhedges can be ignored. We prove the soundness of our compiler based on a nontrivial invariant that we establish (we note that the proof required an adaptation of the original compiler from FCT [24]). We also present a counter-example showing that the safe-no-change projection is not complete for subhedge projection. It shows that a subhedge may be irrelevant even though its state may still be changing. As a second contribution, we propose the congruence projection algorithm. It again compiles Shas to Sha's but relies on the congruence relations of automata states. We then prove that congruence projection yields not only a sound algorithm but that this algorithm is also complete for subhedge projection, i.e., all strongly irrelevant subhedges (see Definition 9) are evaluated into a looping state. Congruence projection starts on the top-level of hedges with the Myhill-Nerode congruence that is well-known from automata minimization.