# Determinization and Minimization of Automata for Nested Words Revisited
## 5 Stepwise Hedge Automata
### Compilation of NREs to SHAs  
As for _NWAs_, we introduce the notion of multi-module _SHAs_ for which the sets of hedge states are partitioned between those that can evaluate top level positions and those to which nested positions are assigned. Therefore, multi-module _SHAs_ will have exactly two modules too. Definition 6: A SHA \(A=(Q_{h},Q_{t},\Sigma,\Delta,I,F)\) is a _multi-module_ SHA if there is a subset of states \(Q_{h}^{0}\subseteq Q_{h}\), that we call _top level states_, such that  
* \(I\subseteq Q_{h}^{0}\) and
* the states in \(Q_{h}^{0}\) can reach only other states in \(Q_{h}^{0}\) via \(\Delta\). For instance, consider the multi-module _SHA_ in Figure 13. The states of module for the top level are \(Q_{0}=\{1,2,3,4,5,6,12\}\). The others belong to the module for the nested level. Figure 14: Determinization of _SHAs_. Figure 15: The determinized _SHA det_\((\operatorname{step}(ch^{*}(a+b)))\). Any \(NRE\)\(E\) can be compiled to a multi-module \(SHA\)\(\text{step}(E)=(Q_{h},Q_{t},\Sigma,\Lambda,I,F)\) such that \(Q_{t}=\{E^{\prime}\mid E^{\prime}=\langle E^{\prime\prime}\rangle\text{ subexpression of }E\}\) and \(L_{t}(E^{\prime})=L(E^{\prime})\) for all tree states \(E^{\prime}\in Q_{t}\). The \(SHA\)\(\text{step}(E)\) can be partitioned into disjoint \(SHA\)s\(\text{step}(E)=A^{top}\cup\bigcup\limits_{E^{\prime}\in Q_{t}}A^{E^{\prime}}\) such that \(A^{top}=(Q_{h}^{top},Q_{t},\Sigma,A^{top},I,F)\) and \(A^{E^{\prime}}=(Q_{h}^{E^{\prime}},Q_{t},\Sigma,\Delta^{E^{\prime}},\emptyset,Q)\) for all \(E^{\prime}\in Q_{t}\) and \(\langle\rangle^{Asp}=\emptyset\). Note that the transitions relation \(\Delta\) is decomposed thereby into independent connected components. The automaton \(A^{top}\) can be identified with an Nfa with signature \(\Sigma\cup Q_{t}\) given that it has no tree initial states. The automata \(A^{E^{\prime}}\) are stepwise tree automata that recognize the tree language \(L(E^{\prime})\) when taking \(E^{\prime}\) as final state. For this, they may have tree initial states, but will not have any initial nor final states. Theorem 4.1: _For any NRE \(E\), we can construct a SHA \(A\) such that \(L(A)=L(E)\). If \(E\) contains neither conjunctions nor negations, then the construction is in time \(O(|E|)\)._  
Proof sketch. : For the case of expressions with conjunctions or negations, the construction is analogous to the way it is done for _NWAs_. We next sketch the construction of \(SHA\)s for expressions without conjunction and negation. **Case \(E=E^{\prime}\cdot E^{\prime\prime}\):**: We use McNaughton-Yamada-Thompson algorithm [PERSON] (1976) for composing the multi-module \(\textsc{Nfa}\)s of \(\text{step}(E^{\prime})\) and \(\text{step}(E^{\prime\prime})\). The stepwise tree automata \(A^{\langle E^{\prime\prime}\rangle}\) of the subexpressions of type tree are preserved. For succinctness, if some subexpression \(\langle E^{\prime\prime\prime}\rangle\) occurs more than once, then only a single copy of \(A^{\langle E^{\prime\prime}\rangle}\) is kept. References to states of the removed copy should be renamed to their equivalent counterparts. **Case \(E=\langle E^{\prime}\rangle\):**: We construct \(\text{step}(E)\) from \(\text{step}(E^{\prime})\). The initial states of \(\text{step}(E^{\prime})\) are turned into tree initial states. We then add a new tree state \(\langle E^{\prime}\rangle\) and connect it to all final states of \(\text{step}(E^{\prime})\) by a tree final rule \(q\longrightarrow\langle E^{\prime}\rangle\). Furthermore, the previously final state \(q\) becomes non final. Finally we add a new initial state \(q_{i}\), a new final state \(q_{f}\) and a transition rule \(\stackrel{{ h}}{{\longrightarrow}}\)\(\stackrel{{\langle E^{\prime}\rangle}}{{  
We omit the correctness proof of this construction. Unlike _NWAs_, one cannot preserve the determinism of the expressions of \(nregexp(ch,T)\) in _SHAs_, even with Glushkov-like constructions.