# Determinization and Minimization of Automata for Nested Words Revisited
## 1 Introduction
Thereby, they produce huge deterministic automata even for very simple navigational XPath queries from the benchmark, or do not terminate after some hours. In this article, we consider _NREs_ for defining queries on nested words. For benchmarking with realistic example, we consider the navigational XPath queries in the XPathMark benchmark with only forwards axis, that we compiled to _NREs_ of the same size up to a constant factor. The question is then whether these _NREs_ can be compiled to reasonably small deterministic _NWAs_. As a first approach, we distinguish a subclass of \"deterministic\" _NREs_ that can be compiled in polynomial time to deterministic _NWAs_ by generalizing on [PERSON]'s construction of deterministic finite-state automata (DFAs) from \"deterministic\" regular expressions [19, 20]. However, the _NREs_ obtained by compilation from navigational XPath queries are rarely deterministic, so neither are the _NWAs_ compiled from them. Moreover, as we cannot apply _NWA_ determinization to them in practice as argued above, this first approach has a much too low coverage to reach the objective. Therefore, we will report it only at the end in Section 9. For our second approach, we propose a novel variant of automata for nested words that we call _stepwise hedge automata_ (_SHAs_). Even though motivated by the wish to create deterministic automata for the _NREs_ of our benchmark, they are of general interest:they generalize naturally on both (stepwise) tree automata [21] and on finite word automata. In contrast to stepwise tree automata, _SHAs_ can not only recognize unranked trees, but also sequences thereof, i.e., hedges or nested words. Furthermore, _SHAs_ can be determinized in a bottom-up and left-to-right manner by combining in a natural manner the determinization procedures for tree and word automata. By adapting existing compilers for stepwise tree automata [21], _SHAs_ can be compiled to _NWAs_ with the same language in linear time while preserving determinism. Conversely, _NWAs_ can be compiled to _SHAs_ in polynomial time, but at the cost of introducing non-determinism. By compiling _NWAs_ to _SHAs_, determinizing the _SHA_, and compiling the obtained deterministic _SHA_ back to a deterministic _NWA_, we can determinize _NWAs_ by determinizing the corresponding _SHAs_. This alternative determinization algorithm for _NWAs_ is different from the usual determinization algorithm for _NWAs_[2; 3; 18]. Indeed, it yields reasonably small deterministic _NWAs_ for the _NREs_ from the XPath benchmark. Yet another alternative algorithm for determinizing _NWAs_ can be obtained by compiling _NWAs_ to _SHAs_ and back, and then determinizing the _NWAs_ obtained in this manner. When applied to back-and-forth converted _NWAs_, the usual _NWA_ determinization algorithm turns out to be well behaved: it produces deterministic _NWAs_ of reasonable size for all our benchmark _NREs_. This might be surprising, given that the same determinization algorithm behaved so poorly for the non-converted _NWAs_ that were obtained from the benchmark _NREs_ directly. We contribute two further solutions for producing deterministic _NWAs_ for our benchmark _NREs_. These are both based on a direct compiler from _NREs_ to _SHAs_. We can then determinize these _SHAs_, followed by compilation to deterministic _NWAs_. Otherwise, we can first compile the _SHAs_ to _NWAs_ and then determinize these NWAs. The next question is why the new determinization algorithms for _NWAs_ that use _SHA_s as intermediates work so nicely. In order to understand this, we need to investigate the relationship between _NWAs_ and _SHAs_s more deeply. Clearly, the _NWAs_ obtained via _SHAs_s do all their work in a bottom-up and left-to-right manner, and nothing when moving top-down. We can characterize the subclass of _NWAs_ with this restricted behavior syntactically by the _(weak) single-entry property_: it requires that all opening rules of the _NWAs_ go into into the same target state while popping the sources state onto the stack.