# Determinization and Minimization of Automata for Nested Words Revisited
## 3 Nested Regular Expressions
### Syntax and Semantics  
Let the alphabet \(\Sigma\) be a set. An _NRE_ over \(\Sigma\) is a term describing a language of nested words. It has the following abstract syntax where \(a\in\Sigma\):  
\[E,E^{\prime}::=\varepsilon\mid a\mid_{-}\mid\emptyset\mid E\cdot E^{\prime} \mid E+E^{\prime}\mid E\&E^{\prime}\mid E^{*}\mid\overline{E}\mid\langle E \rangle\mid\mu a.E\]  
The \(\mu a.E\) expressions are the same as in \(\mu\)-calculus [33], except that we restrict them such that all occurrences of \(a\) in \(E\) are nested below parentheses. Otherwise, nonregular  
Figure 4: The nested word of the \(x\)-marked XML document from Figure 2.  
Figure 3: The corresponding nested word.  
languages could be defined such as with \(\mu a\). \((b\cdot a\cdot c+\varepsilon)\) whose language would be \(\{b^{n}\cdot c^{n}\mid n\in\mathbb{N}\}\). We also forbid intersections and complements in expression \(\mu a.E\) on all paths between the \(\mu a\)-operator and the occurrences of \(a\) in \(E\) that are bound by this operator. The expressions \(\mu a.E\) allow for vertical recursion, while the expressions with the Kleene star \(E^{*}\) support horizontal recursion.  
Our syntax allows for conjunctions \(E\&E^{\prime}\) and negations \(\overline{E}\), which are well known to not add expressiveness if \(\Sigma\) is finite. They are still relevant from the viewpoints of modeling, and for the treatment of infinite signatures. This comes at the price of increasing the complexity, as for the well-known case of words [34].  
For infinite signatures, we can define for any finite subset \(\Sigma^{\prime}\) of labels the language of single-letter words \(\Sigma\setminus\Sigma^{\prime}\) by some \(NRE\). This can be seen as follows. If \(\Sigma^{\prime}=\emptyset\), then the expression _ does the job: it matches exactly the set of all labels in \(\Sigma\). Moreover, if \(\Sigma^{\prime}\) is nonempty then we can use negation. For instance, if \(\Sigma^{\prime}=\{a,b\}\) then the expression \(\overline{a+b}\&_{-}\) describes the language \(\Sigma\setminus\Sigma^{\prime}\).  
The sets of free and bound letters \(\mathit{fn}(E)\) and \(\mathit{bn}(E)\) are defined as usual. The only binder \(\mu a.E\) binds the symbol \(a\) with scope \(E\). Note that \(\mathit{fn}(\_)=\emptyset\).  
There are three differences with respect to the regular expression types from [10]. First, our \(NRE\) treat labels as internal symbols instead of labels of parentheses. Second, they provide recursion through the \(\mu\)-operator instead of using recursive equation systems. Third, conjunctions and general negations are not considered there.  
Any \(NRE\) describes a language \(L(E)\) of nested words that we define by induction on the structure of \(E\) as follows: \(\mathcal{N}_{\Sigma}\) is the set of nested words over \(\Sigma\), as defined in Section 2.  
\[\begin{array}{ll}L(\varepsilon)=\{\varepsilon\}&L(a)=\{a\}&L(\_)=\Sigma\\ L(E\cdot E^{\prime})=L(E)\cdot L(E^{\prime})&L(\overline{E})=\mathcal{N}_{ \Sigma}\setminus L(E)\\ L(E+E^{\prime})=L(E)\cup L(E^{\prime})&L(E\&\varepsilon E^{\prime})=L(E)\cap L (E^{\prime})\\ L(\langle E\rangle)=\{\langle h\rangle\mid h\in L(E)\}&L(\mu a.E)=\cup_{n\geq 0 }L(u^{n}a.E)\\ L(E^{*})=L(E)^{*}&L(\emptyset)=\emptyset\end{array}\]  
For all expressions--\(E\), \(E_{1}\), and \(E_{2}\), the notation \(E[E_{1}/E_{2}]\) stands for the expression \(E\) where all the occurrences of \(E_{1}\) have been replaced by \(E_{2}\). The semantics of a \(\mu\)-operator is then defined using the shortcuts \(\mu^{0}a.E=E[a/\emptyset]\) and \(\mu^{n}a.E=E[a/\mu^{n-1}a.E]\) for all \(n\geq 1\). In particular \(L(\mu a.\_)=L(\_)=\Sigma\), so that \(a\in L(\mu a.\_)\). The semantics of the complement expression \(L(\overline{E})\) is the complement of \(L(E)\) in the set of all nested words, that is \(\mathcal{N}_{\Sigma}\setminus L(E)\).