# Determinization and Minimization of Automata for Nested Words Revisited
## 9 Deterministic Nested Regular Expressions  
We finally show how to distinguish _NREs_ that can be evaluated deterministically in polynomial time, for instance, by compilation to deterministic _NWAs_. For this, we consider the language of _NREs__nregexp\((ch,T)\)_ that extends the abstract syntax of _NREs_ by a new constant \(T\) and a new unary operator \(ch\).  
Definition 8: An expression of _nregexp\((ch,T)\)_ is deterministic if it does not contain a subexpression of any of the forms: \(E_{1}+E_{2}\), \(E^{*}\), \(T\cdot E\), \(\mu a.E\).  
Note in particular that \(ch(a)\) is a deterministic expression of _nregexp\((ch,T)\)_, as the child operator is added as a primitive there. In contrast, the semantically equivalent expression \(T\cdot\langle a\rangle.T\) is not deterministic. Similarly, \(T\) is deterministic since it is a primitive expression of _nregexp\((ch,T)\)_, while the equivalent expression \(\mu x.(\langle x\rangle+_{-})^{*}\) is nondeterministic for three different reasons: the \(\mu\)-operator, star \(*\), and disjunction \(+\). The recursive expression \(ch^{*}(E)\) is nondeterministic: it is not primitive in _nregexp\((ch,T)\)_, and its definition is based on the \(\mu\)-operator and disjunction.  
The only query of the benchmark for which we can provide a deterministic _NRE_ is the query A1. The _NRE_ for query A1 in Figure A1 is nondeterministic nevertheless, as we replaced \(ch(E)\) with \(T\cdot\langle E\rangle\cdot T\). This is not problematic, given that we can use a decent method for determinization of _NWAs_. For this reason, it does no more seem worth the effort to maintain specialized compilation methods for deterministic _NREs_. For the same reason, we will not present any experimental results for our specialized compiler from deterministic _NREs_ to deterministic _NWAs_. Instead we use the more general compiler for general nondeterministic _NREs_.  
The compiler from Theorem 1 introduces epsilon rules, and thus it does not preserve determinism: some deterministic _NREs_ will be compiled to nondeterministic _NWAs_.  
Figure 27: Deterministic _NWAs_ for the queries \(ch^{n}(a)\) where \(n=0,\ldots,9\): size (#states). There is no schema-based cleaning. Our implementation of the minimization algorithm was applied to all _dSHA_ with at most 200 states, as it failed for larger _dSHAs_. No minimization algorithm for subclasses of single-entry _dNWAs_ was implemented.  
This introduction of nondeterminism can be avoided by eliminating epsilon rules on the fly, that is by using [PERSON]'s approach rather than that of [PERSON].  
For any deterministic regular expression \(E\) of \(\mathit{nregexp}(\mathit{ch},T)\) without conjunction and negation, we can construct in time \(O(|E|^{2})\) a dNWA recognizing the same language.  
Proof sketch.: Theorem 3 uses [PERSON]'s construction and thus eliminates \(\varepsilon\)-edges on the fly compared to the McNaughton-Yamada-Thompson algorithm. The Glushkov construction is well-known to preserve determinism when compiling regular expressions without nesting to finite state automata [20]. For the additional deterministic expressions \(\mathit{ch}(E)\), we adapt the deterministic compilation from the work in [18]. This quadratic time result generalizes a previous result for the Glushkov construction [19] from regular expressions without conjunctions and negations to \(\mathit{NREs}\) without conjunctions and negations.  
Small deterministic \(\mathit{NREs}\) without conjunction and negation can thus be compiled to small \(\mathit{dNWA}\)s. On the benchmark, however, this construction can be applied to the query \(A1\) only, so only a few queries can be covered in this manner.