# Complete Subhedge Projection for Stepwise Hedge Automata +
## 1 Introduction  
Hedges are sequences of letters from the alphabet and trees \(\langle h\rangle\) where \(h\) is again a hedge. Hedges are abstract from the syntactical details of Xml or JSON documents while still being able to represent them. The linearization of a hedge is a nested word that can be written in a file. In this article, we study the problem of hedge pattern matching, i.e., whether a given hedge \(h\) belongs to a given regular hedge language \(L\). Regular hedge languages can be defined in XPath or JSONPath in particular. Projection is necessary for the efficiency of many algorithms on words, trees, hedges, or nested words. Intuitively, an algorithm is projecting if it visits only a fragment of the input structure: in the best case, the part that is relevant to the problem under consideration. The relevance of projection for Xml processing was already noticed by [1; 2; 3; 4]. Saxon's in-memory evaluator, for instance, projects input Xml documents relative to an Xslt program, which contains a collection of XPath queries to be answered simultaneously [5]. The QuiXPath tool [4] evaluates XPath queries in streaming mode with subtree and descendant projection. Projection during the evaluation of JSONPath queries on JSON documents in streaming mode is called fast-forwarding [6]. Projecting in-memory evaluation assumes that the full graph of the input hedge is constructed beforehand. Nevertheless, projection may still save time if one has to match several patterns on the same input hedge or if the graph was constructed for different reasons anyway. In streaming mode, the situation is similar: the whole input hedge on the stream needs to be parsed, but the evaluators need to inspect only nodes that are not projected away. Given that pure parsing is by two or three orders of magnitude faster than pattern evaluation, the time gain of projection may be considerable. The starting point of this article is the notion of the subhedge irrelevance of positions of hedge \(h\) with respect to a hedge language \(L\) that we introduce. These are positions of \(h\) where, for all possible continuations, inserting any subhedge does not affect membership to \(L\). We contribute an algorithm for hedge pattern matching with complete subhedge projection. Our algorithm decides hedge pattern matching while completely projecting away the subhedges located at irrelevant subhedge positions. In other words, it decideswhether a hedge \(h\) matches a pattern \(L\) without visiting any subedge of \(h\) that is located at a position that is irrelevant with respect to \(L\). Regular hedge languages can be represented by nested regular expressions, which can be derived from regular XPath queries [7] or by some kind of hedge automata, which can be compiled from nested regular expressions. We use stepwise hedge automata (Shas) [8], a recent variant of standard hedge automata, which, in turn, date back to the 1960s [9; 10]. Shas mix up the bottom-up processing of standard tree automata with the left-to-right processing of finite word automata (Dfas). They neither support top-down processing nor have an explicit stack, unlike nested word automata Nwas[11; 12; 13; 14; 15]. Shas have a good notion of bottom-up and left-to-right determinism, avoiding the problematic notion of determinism for standard hedge automata and the too-costly notion of determinism for Nwas. Furthermore, compilers from nested regular expressions to Shas are available [8], and determinization algorithms [16] produce small Shas for all regular XPath queries in the existing practical benchmarks [7; 17]. The motivation for the present work is to add subedge projection to a recent streaming algorithm for deterministic Shas that can evaluate regular XPath queries in the earliest manner. Most alternative streaming approaches avoid earliest query answering by considering sublanguages of regular queries without delays so that node selection depends only on the past of the node but not on the future [18; 19] or by admitting late selection [20].