# Parsing Unranked Tree Languages, Folded Once +
## 3 Regular Tree Foldings  
The purpose of the folding operation is to turn an unranked tree \(t\) over an alphabet \(\Sigma\) into a graph \(g\) by merging nodes. The folding is performed by marking nodes with symbols from an auxiliary alphabet \(\Delta\), meaning that some nodes will have labels in \(\Sigma\times\Delta\), and then, for each \(\alpha\in\Delta\) merging all nodes marked with symbols in \(\Sigma\times\{\alpha\}\) into a single node with a label in \(\Sigma\). The reason for removing the folding symbol of the node resulting from a merging is to prevent it from being folded together with other nodes later on in the process, which would complicate parsing. By itself, this formalism can only produce output graphs where, at most, \(|\Delta|\) nodes have more than one incoming edge. For this reason, the merging is divided into _scopes_ by allowing for nodes in \(t\) that have labels from \(\Delta\): a node \(u\) in \(t\) labelled \(\alpha\in\Delta\) is an instruction that all nodes with labels in \(\Sigma\times\{\alpha\}\)_below it_ are to be merged, whereupon the node \(u\) itself is to be deleted. The tree is then evaluated bottom-up, so that \(\Delta\)-labelled nodes lower in the tree have their corresponding operations performed earlier. To keep the result well-defined, the tree language must force nodes with labels in \(\Delta\) to have exactly one direct subtree. The combination of a regular unranked tree language over \(\Sigma\cup(\Sigma\times\Delta)\cup\Delta\) and a fold operation over \(\Delta\) is called a _regular tree folding_. The folding operation is illustrated in Figure 1. In the original definition [18], the label of the merged node \(v\) is chosen non-deterministically based on the labels of the nodes that went into the merger. However, there is a (less compact) normal form of regular tree foldings, which only merges nodes if they share the same label \((\sigma,\alpha)\in\Sigma\times\Delta\), and the resulting node in the output graph is then labelled \(\sigma\)[19]. This paper is only concerned with the case where there is a single folding symbol, and the normal form allows us to assume that there is a unique \(\langle\sigma,\alpha\rangle\in\Sigma\cup\Delta\) that is allowed by the regular tree language. Thus, throughout this paper, let \(\Sigma\) be an alphabet, let \(\sigma\in\Sigma\), and let \(\alpha\) be a special symbol not in \(\Sigma\). We write \(\Gamma\) for the alphabet \(\Sigma\cup\{\langle\sigma,\alpha\rangle,\alpha\}\). **Definition 1** (The fold operation \(F\)). : _The function \([\![\alpha]\! ]\colon\mathbb{G}_{\Gamma}\to\mathbb{G}_{\Gamma}\) takes a single-rooted input graph \(g=(V,E,\mathit{src},\mathit{tar},\mathit{lab},r)\in\mathbb{G}_{\Gamma}\) and computes an output graph \(h=[\![\alpha]\! ](g)\) by merging the set of nodes \(\mathit{nodes}(g)_{\langle\sigma,\alpha\rangle}\) into a single node \(u\), and assigning \(u\) the label \(\sigma\). If \(\mathit{root}(g)\in\mathit{nodes}(g)_{\langle\sigma,\alpha\rangle}\), then \(\mathit{root}(h)=u\); otherwise \(\mathit{root}(h)=\mathit{root}(g)\). The fold operation \(F:\mathrm{T}_{\Gamma}\to\mathbb{G}_{\Gamma}\) is defined for every tree \(t=\gamma[t_{1},\dots,t_{k}]\in\mathrm{T}_{\Gamma}\) by \(F(t)=[\![\gamma]\! ](F(t_{1}))\) if \(\gamma=\alpha\) (when \(k\) is always \(1\)), and \(\gamma[F(t_{1}),\dots,F(t_{k})]\) otherwise. It is extended to sets of trees in the expected way: for \(L\subseteq\mathrm{T}_{\Gamma}\), \(F(L)=\bigcup_{t\in L}\{F(t)\}\)._By combining the fold operation with a regular tree language, we reach our formalism of interest. **Definition 2** (Regular tree folding (with one folding symbol)). : _A regular tree folding (RTF) over \(\Gamma\) is defined through a \(Z\)-automaton \(A\) over the same alphabet, such that, for every \(t\in\mathcal{L}(A)\) and every node \(v\) in \(t\), it holds that if the label of \(v\) is \(\alpha\), then \(v\) has exactly one direct subtree. The folded graph language with respect to \(A\) is \(\mathcal{L}_{F}(A)=F(\mathcal{L}(A))\)._  
**Example 1**.