# Complete Subhedge Projection for Stepwise Hedge Automata +
## 9 Streaming Algorithms
### Streaming Evaluators for Downward Hedge Automata  
We define the streaming evaluator of a Sha\({}^{\downarrow}\)\(A=(\Sigma,\mathcal{Q},\Delta,I,F)\) by a visibly pushdown machine. The set of configurations of this machine is \(\mathcal{K}=\mathcal{Q}\times\mathcal{Q}^{*}\), containing pairs of states and stacks of states. The visibly pushdown machine provides for any word \(v\in\hat{\Sigma}^{*}\) a streaming transition relation \(\overset{v}{\rightarrow}\overset{str}{\rightarrow}\subseteq\mathcal{K}\times \mathcal{K}\), such that for all states \(q,q^{\prime}\in\mathcal{Q}\) and stacks \(\sigma\in\mathcal{Q}^{*}\) and words \(v,v^{\prime}\in\hat{\Sigma}^{*}\):  
\[ \begin{array}{c}\infer{true}{(q,\sigma)\overset{v}{\rightarrow}\overset{ str}{\rightarrow}(q,\sigma)\text{ wrt }\Delta}\\ \infer{(q,\sigma)\overset{v}{\longrightarrow}\overset{str}{\rightarrow}(q^{ \prime},\sigma)\text{ wrt }\Delta}\\ \infer{q\overset{a}{\rightarrow}q^{\prime}\text{ in }\Delta}{q\overset{s}{ \rightarrow}\overset{str}{\rightarrow}q^{\prime}\text{ wrt }\Delta}\\ \infer{(q,\sigma)\overset{v}{\longrightarrow}\overset{str}{\rightarrow}(q^{ \prime},\sigma)\text{ wrt }\Delta}\end{array} \qquad\infer{(q,\sigma)\overset{v}{ \rightarrow}\overset{str}{\rightarrow}(q^{\prime},\sigma)\text{ wrt }\Delta}{q\overset{v}{\rightarrow}\overset{str}{\rightarrow}(q^{\prime}, \sigma)\text{ wrt }\Delta}\]  
We note that the same visibly pushdown machine can be obtained by compiling the Sha\({}^{\downarrow}\) to an Nwa, whose streaming evaluator is defined by a visibly pushdown machine too (see Section 12.3 on related work). The notion of partial runs of the in-memory evaluator is closely related to streaming runs. To see this, we first note that each partial run \(v\) wrt \(\Delta\) naturally defines a stack as follows. Since \(v\) is a nested word prefix, there exist unique nested words \(v_{0},\ldots,v_{n}\in\mathit{nw}(\mathcal{H}_{\Sigma\cup\mathcal{Q}})\), such that  
\[v=v_{0}\cdot\big{\langle}\cdot v_{1}\cdot\big{\langle}\cdot\ldots\cdot\big{ }\cdot v_{n}.\]  
These nested words must be partial runs of \(\Delta\) too, so there exist states \(p_{0},\ldots p_{n},q_{0},\ldots,q_{n}\in\mathcal{Q}\), such that \(v_{i}\) goes from \(p_{i}\) to \(q_{i}\) for all \(0\leq i\leq n\). We define the stack \(\sigma\) of \(v\) by \(\sigma=q_{0}\cdot\ldots\cdot q_{n-1}\) and say that \(v\) goes from \(p_{0}\) to \(q_{n}\) and has stack \(\sigma\). Note that the stack is empty if \(v\) is a nested word, since in this case \(n=0\) so that \(v=v_{0}\) and \(\sigma=\varepsilon\). For instance, the partial run \(v_{0}=0\cdot\big{\langle}\cdot 0\cdot list\cdot\big{\langle}\cdot 0\cdot item \cdot 2\text{ has the stack }\sigma_{0}=0\cdot 1\text{ while the partial run }v_{1}=v_{0}\cdot\big{\rangle}\cdot 3\cdot\big{\rangle}\cdot 4\) has stack \(\sigma_{1}=\varepsilon\). **Lemma 20**. : _Consider a Sha\(A=(\Sigma,\mathcal{Q},\Delta,I,F)\), states \(q,q^{\prime}\in\mathcal{Q}\), and a stack \(\sigma\in\mathcal{Q}^{*}\). Let \(v\) be a prefix of some nested word in \(\mathit{nw}(\mathcal{H}_{\Sigma})\). Then, there exists a partial run \(r\) wrt \(\Delta\) from \(q\) to \(q^{\prime}\) with stack \(\sigma\) such that \(\mathit{proj}_{\Sigma}(r)=v\) iff \((q,\varepsilon)\overset{v}{\rightarrow}\overset{str}{\rightarrow}(q^{\prime}, \sigma)\) wrt \(\Delta\)._  
Proof. : This is carried out by induction on the length of prefix \(v\). This lemma implies that any in-memory transition of \(A\) on a hedge \(h\) from \(q\) to \(q^{\prime}\) can be identified with some streaming transition of \(A\) on \(\mathit{nw}(h)\) from \((q,\varepsilon)\) to \((q^{\prime},\varepsilon)\). **Proposition 8**. : \(q\overset{h}{\rightarrow}q^{\prime}\)_wrt \(\Delta\Leftrightarrow(q,\varepsilon)\overset{\mathit{mw}(h)}{\longrightarrow} \overset{str}{\rightarrow}(q^{\prime},\varepsilon)\) wrt \(\Delta\)._  
**Proof. ** If \(q\xrightarrow{h}q^{\prime}\) wrt \(\Delta\), there exists a run \(R\) of \(h\) with \(\Delta\) that starts with \(q\) and ends with \(q^{\prime}\).