# Determinization and Minimization of Automata for Nested Words Revisited
## 7 Optimizations
### Minimization  
Our next objective is to reduce the size of deterministic _SHA_s by developing a minimization algorithm for a subclass of _dSHA_s. Even though our implementation can deal with them, we consider _SHA_s without symbolic rules \(q\xrightarrow{\sim}q^{\prime}\) for simplicity in this section. We start with an example that motivates the choice of our subclass. In Figures 21 and 22, two _dSHA_s are given that both recognize the language of all hedges with signature \(\Sigma=\{x,y\}\) containing exactly one occurrence of the letter \(x\). The _dSHA_ in Figure 22 is the _dSHA_ recognizing this language which has the minimal number of states. The _dSHA_ in Figure 21 is the minimal multi-module _dSHA_ for this language. The question is how a minimization algorithm for _dSHA_s could convert the _dSHA_ in Figure 21 to this minimal one in Figure 22. In particular, why would it merge the tree initial state and the hedge initial state? We do not see how this could be done based on some Myhill-Nerode-like equivalence relation. This motivates an a priori restriction to _dSHA_s imposing that the tree initial state and hedge initial state must be equal. Figure 21: A _dSHA_ for hedges over \(\Sigma=\{x,y\}\) with single occurrence of \(x\). It is minimal in the class of multi-module _dSHA_s. Note that any _SHA_ can be converted into a _dSHA_ with equal tree and hedge initial states. For this, it is sufficient to \"fuse\" these states and then to determinize the _SHA_ obtained. When doing so for the _dSHA_ in Figure 21, we indeed obtain the minimal _dSHA_ from Figure 23, so no further minimization is needed in this case. Given the close relationship between _SHA_s and weak single-entry _NWAs_, it is instructive to consider the existing results on minimization for _dNWAs_. It is known that the class of general _dNWAs_ does not allow for unique minimization [22] and that the minimization becomes NP-hard when admitting general signatures with multiple parenthesis [24]. On the positive side, the best existing minimization algorithm is due to [PERSON] and [PERSON] [23]. It applies to the subclass of _multi-module single-entry dNWAs_, called there _call-driven automata (CDA)_ ([PERSON] and [PERSON] [23] permit signatures with multiple opening parenthesis. In the case of a single opening parenthesis, the class of CDAs is equal to their subclass of _expanded CDAs_ for which they develop their minimization algorithm in the first place.). They showed that the subclass of multi-module single-entry _dNWAs_ enjoys unique minimization in polynomial time. In the case of _dSHA_s, we believe that unique minimization holds for the following two subclasses, and will show it for the second:  
* the subclass of multi-module _dSHA_s, and
* the subclass of _dSHA_s where the hedge and tree initial state are the same, i.e., \(\langle\rangle^{\Delta}=I\). The first subclass of multi-module _dSHA_s is motivated by the subclass of multi-module single-entry _dNWAs_. Note, however, that the _SHA_s that are obtained by compilation from single-entry _dNWAs_ need not be deterministic, so the analogy between both automata classes is not perfect. The _dSHA_ in Figure 21 is minimal for the class of multi-module _dSHA_s. The second subclass of _dSHA_s corresponds to the subclass of single-entry _dNWAs_ in which the single-entry state is equal to the initial state. The _dSHA_ in Figure 22 is minimal for the second subclass. In the remainder of this section, we present a minimization algorithm for the second subclass. For this, we identify _dSHA_s in which tree and hedge initial state coincide with two-sorted deterministic tree automata, so that we can use a minimization algorithm for the latter. Our automaton translation is based on a novel encoding of hedges into ranked well-sorted trees with monadic and binary function symbols, which is inspired by the previous binary encoding of unranked trees known from stepwise tree automata [21].