# Determinization and Minimization of Automata for Nested Words Revisited
## 1 Introduction  
Nested words are hierarchical structures that are omnipresent in computer science. They were used to represent sequences of data trees, like XML or JSON documents, and to analyze the call structure of recursive programs. The idea of nested words is to generalize on both words and trees, resulting in sequences of unranked trees that are also known as hedges. Otherwise, nested words can be obtained by enriching Dyck words with internal letters, besides opening and closing parentheses. Furthermore, nested words are the elements of the least set containing internal letters from a given alphabet, triples consisting of an opening parenthesis, a nested word, and a closing parenthesis, and all sequences of nested words. Last but not least, nested words can be seen as words over an alphabet with internal letters, opening parentheses, and closing parentheses, under the conditions thatthe parenthesis are well nested, so that every opening parenthesis is properly closed and every closing parenthesis properly opened. From the viewpoint of formal language theory, a natural question is how to lift the notions of finite automata and regular expressions, from words and trees to nested words, while preserving their well-known relationships. _Nested word automata_ (_NWAs_) were heavily studied since the 1980s [1, 2, 3, 4], under the name _input-driven automata_. They are the same as _visibly pushdown automata_[5], _pushdown forest automata_[6], and _streaming tree automata_[7]. _NWAs_ can recognize the same languages of unranked trees as hedge automata [8], a generalization of tree automata for ranked trees [9]. _NWAs_ are often defined as pushdown automata with visible stacks, meaning that exactly one symbol is pushed when reading an opening parenthesis, and exactly one symbol is popped when reading a closing parenthesis, while the stack is not used otherwise. Their main advantage is a powerful notion of determinism, generalizing both over bottom-up and top-down determinism of tree automata for ranked trees [2, 3]. We note that general pushdown automata do not permit determinization in contrast. Regular expressions for nested words were proposed more recently by [PERSON] and [PERSON] [10] under the name of _regular expression types_. In the present article, we will call them _nested regular expressions_ (_NREs_) instead. Independently, more complex notions of nested regular expressions were introduced [11, 12] in order to deal with generalizations of nested words with dangling opening and closing parentheses, which are not of interest to us. It was already claimed in [10], that our simpler notion of _NREs_ has the same expressiveness as hedge automata [8, 9], which in turn have the same expressiveness as _NWAs_[3]. However, the question under which conditions _NREs_ can be compiled to small deterministic _NWAs_ has not been studied. For classes of _NREs_ for which deterministic _NWAs_ can be computed in polynomial time, we can decide language inclusion or equivalence in polynomial time too. For other classes, these problems may not be feasible since language inclusion for nondeterministic _NWAs_ is EXP-complete. Our concrete interest in the universality of deterministic _NWAs_ is motivated by XML stream processing: we want to compute the certain answers of a navigational XPath query on an XML stream [13, 14], i.e., those elements that are selected in all possible futures of the stream. Whether an answer is certain is computationally hard, even for tiny syntactic fragments of navigational XPath [14, 15], but can be done in polynomial time for queries defined by deterministic _NWAs_[16]. A natural question is, therefore, whether it is possible to compile navigational XPath queries as in the usual benchmark [17] to deterministic _NWAs_ of reasonable size. Unfortunately, the existing compilers fail to do so [18], as they are based on _NWAs_ determinization for dealing with disjunction, negation, and recursive steps.