# Determinization and Minimization of Automata for Nested Words Revisited
## 1 Introduction
Note that our single-entry property is weaker than the _(multi-module) single-entry property_ studied previously [22; 23; 24], which in addition requires that the automaton can be split into at least 2 modules, one for the top level and one for the nested level. The _NWAs_ obtained by compilation from _SHAs_ all have the (weak) single-entry property (but not necessarily multiple modules). Therefore, when compiling _NWAs_ to _SHAs_ and back, the resulting _NWAs_ also have the (weak) single-entry property. It seems that the usual determinization algorithm from _NWAs_ is well-behaved when applied to _NWAs_ with the (weak) single-entry property. The relationship between _SHAs_ and (weak) single-entry _NWAs_ seems sufficiently close, so that their determinization algorithms seem to operate in somehow similar manners. It is known that the subclass of deterministic multi-module single-entry _NWAs_ (also called _call-driven automata_) enjoys unique minimization [22; 23]. The separation of the module for the top level from the module for the nested level can be obtained w.l.o.g., by building a product with the _NWA_ with two hedge states that distinguishes the two levels. In our application, minimization could thus be used to reduce the size of the deterministic _NWAs_ produced by our four algorithms for converting _NREs_, with the hope to eventually obtain a unique outcome after minimization. However, as we will use some symbolic representations for sets of rules, the uniqueness will hold only for the non-symbolic counterpart. In any case, the number of states of the deterministic minimal _NWAs_ obtained for the same _NRE_ could be expected to become unique. Motivated by our application, we found it more relevant to minimize deterministic _SHAs_ rather than deterministic (weak) single-entry _NWAs_ (despite of their close correspondence). As for the class of deterministic (weak) single-entry _NWAs_, a restriction is neededfor the class of deterministic _SHAs_ to obtain unique minimization. We could have required the existence of multiple modules as for multi-module single-entry _NWAs_. Instead, we restrict ourselves to deterministic _SHAs_ for which the initial states for trees and hedges coincide. We then show that minimization for such _SHAs_ can be reduced to the minimization of tree automata up to a novel encoding of hedges to binary trees. We implemented all four algorithms for compiling our benchmark _NREs_ to deterministic _NWAs_ and report the experimental results. We have also implemented the novel minimization algorithm for _SHAs_ with equal tree and hedge initial states, and used it in our experiments. We propose two further optimization methods for reducing the sizes of the constructed automata. First, we introduce schema-based cleaning both for _SHAs_ and _NWAs_. In our application, the schema expresses the Xml data model, stating that hedges must encode valid Xml documents. More generally, an automaton \(A\) can be cleaned relative to an automaton \(S\) for the schema, if the language of interest is the intersection \(L(A)\cap L(S)\) rather than \(L(A)\) itself. The idea of schema-based cleaning is to keep only those transition rules of \(A\) that are used to recognize some hedge of \(L(S)\). These transition rules can be computed from the product of \(A\) and \(S\). Note that schema-based cleaning may change the language of the automaton. Only the intersection \(L(A)\cap L(S)\) is preserved, not necessarily \(L(A)\). Second, we propose a symbolic representations for _SHAs_ based on apply-else rules. They help to represent more compactly a large number of apply rules produced by the determinization of _SHAs_. Before compiling _SHAs_ to _NWAs_, however, we need to eliminate the apply-else rules. This is because we have not developed analogous symbolic representations for _NWAs_ so far. A second limitation is that we have not implemented any minimization algorithm for _NWAs_ at the time being.