# Complete Subhedge Projection for Stepwise Hedge Automata +
## 1 Introduction
For languages with words \(L\), this congruence identifies prefixes \(v\) that have the same residual language \(v^{-1}(L)=\{w\mid v\cdot w\in L\}\). A prefix \(v\) is then an irrelevant suffix if its residual language \(v^{-1}(L)\) is either universal or empty. In the case of hedges, which extend on words by adding hierarchical nesting via a tree constructor, the congruence must be adapted when moving down into subtrees. We show that both compilers may increase the size of the automata exponentially since they must be able to convert bottom-up deterministic automata on monadic trees into top-down deterministic automata. That is the same as inverting deterministic automata on words, which is well known to raise an exponential blow-up in the worst case (e.g., for the family of languages \((a+b)^{*}\cdot a\cdot(a+b)^{n}\), where \(n\in\mathbb{N}\), the minimal deterministic left-to-left automaton, has \(2^{n+1}\) states while the minimal deterministic right-to-left automaton has \(n+1\) states). The exponential explosion can be avoided when interested in the evaluation of hedges by automaton with subhedge projection, by not constructing the complete Sha's statically. Instead, only the required part of the Sha's may be constructed on the fly when evaluating a hedge. Our third contribution is the refinement of the two previous compilers so that they can also distinguish safe states for selection at the earliest position. For this, we combine these compilers with a variant of the earliest membership tester of [21] that operates in memory by compiling Sha's instead of Nwas. Furthermore, membership failure is detected at the earliest position, too. In this way, we obtain the earliest in-memory membership tester for deterministic Shas. Our fourth contribution is to show how to run the previous in-memory evaluators in streaming mode while reading the linearization of the hedge into a nested word as an input. Thereby, we can improve on the recent earliest streaming membership tester behind the AStream tool [21] by adding subhedge projection to it. Our fifth and last contribution is an implementation and experimental evaluation of the streaming earliest query answering algorithm for dShas by introducing subhedge projection into the AStream tool [21]. We implemented both safe-no-change and congruence projection. For this, we lifted our earliest membership tester with subhedge projection to an earliest query answering algorithm for monadic queries. For the experimentation, we started with deterministic Shas constructed with the compiler from [8] for the forward regular XPath queries of the XPathMark benchmark [27] and real-world XPath queries [7]. It turns out that congruence projection projects much more strongly than the safe-no-change projection for at least half of the benchmark queries. It reduces the running time for all regular XPath queries considerably since large parts of the input hedges can be projected away. In our benchmark, the projected percentage ranges from 75.7% to 100% of the input stream. For XPath queries that contain only child axes, the earliest query answering algorithm of AStream with congruence projection becomes competitive in efficiency with the best existing streaming tool called QuiXPath [23], which is not always earliest for some queries. Our current implementation of the earliest congruence projection in AStream is by a factor from 1.3 to 2.9 slower than QuiXPath on the benchmark queries. The improvement is smaller for XPath queries with the descendant axis, where less subhedge projection is possible. Instead, some kind of descendant projection would be needed. Still, even in the worst case in our benchmark, the earliest congruence projection with AStream is currently only by a factor of 13.8 slower than QuiXPath. **Outline**. We start with preliminaries on hedges and nested words in Section 2. In Section 3, we recall the problem of hedge pattern matching and formally define irrelevant subhedges.