# Parsing Unranked Tree Languages, Folded Once +
## 2 Preliminaries  
This section recalls relevant formal language theory and fixes notation. Central definitions have been lifted from the introduction of regular tree foldings in [18; 19]. The set of non-negative integers is denoted by \(\mathbb{N}\). For \(i\in\mathbb{N}\), \([i]=\{1,\ldots,i\}\) and \([0]=\emptyset\). A _multiset_\(S^{\prime}\) is a set in which elements can have multiple instances. **Graphs:** To allow parallel edges, we define our graphs in terms of source and target mappings. An _alphabet_ is a finite nonempty set of symbols. Let \(\Sigma\) be an alphabet. A (directed and rooted) _graph_ (note that graphs of this type are usually referred to as _rooted multigraphs_ in the literature, but since they are the only kind that we will be concerned with, we opt to simply refer to them as 'graphs') over \(\Sigma\) is a tuple \(g=(V,E,src,tar,lab,r)\) consisting of: finite sets \(V\) and \(E\) of _nodes_ and _edges_, respectively; _source_ and _target mappings_\(src\colon E\to V\) and \(tar\colon E\to V\) assigning to each edge \(e\) its source \(src(e)\) and target \(tar(e)\); a _labelling lab_: \(V\to\Sigma\); and a _root_ node \(r\in V\). The set of _incoming edges_ of \(u\in V\) is \(in(u)\), and the set of _outgoing edges_ is \(out(u)\). The _in-degree_ of \(u\) is \(|in(u)|\), and the _out-degree_ of \(u\) is \(|out(u)|\). A node with an out-degree \(0\) is a _leaf_. The _size_ of the graph \(g\) is \(|g|=|V|+|E|\). The set of all graphs with node labels in \(\Sigma\) is denoted by \(G_{\Sigma}\). We write \(root(g)\) for the root node \(r\), and \(nodes(g)_{\sigma}\) for the set of nodes in \(g\) that are labelled \(\sigma\in\Sigma\). An _edge-ordered graph_ over \(\Sigma\) is a pair \((g,<)\), where \(g=(V,E,src,tar,lab,r)\) in \(G_{\Sigma}\) and \(<\) is a binary relation on \(E\) that becomes a total order when restricted to any set \(in(v)\) or \(out(v)\), for \(v\in V\). From here on, we leave the second component implicit and refer to it as \(<_{g}\) when needed. The set of all edge-ordered graphs over \(\Sigma\) is denoted by \(G_{\Sigma}^{<}\). A _path_ in the graph \(g=(V,E,src,tar,lab,r)\) is a finite and possibly empty sequence \(p=e_{0}e_{1}\cdots e_{k}\) of edges such that, for each \(i\in[k]\), the target of \(e_{i-1}\) is the source of \(e_{i}\). Here, we say that is a path from \(src(e_{0})\) to \(tar(e_{k})\). The path \(p\) is a _cycle_ if \(src(e_{0})=tar(e_{k})\). **Trees:** Let \(\Sigma\) be an alphabet. An _ordered unranked tree over_\(\Sigma\) is a tuple \(t=((V,E,src,tar,lab,r),<)\in G_{\Sigma}^{<}\), such that (i) \(t\) is connected, (ii) \(r\) has no incoming edges, and (iii) every node except for \(r\) has exactly one incoming edge. We denote the set of all ordered unranked trees over \(\Sigma\) by \(\Gamma_{\Sigma}\). Let \(\sigma\in\Sigma\), \(k\in\mathbb{N}\), and \(t_{1},\ldots,t_{k}\) be trees over \(\Sigma\). Moreover, for each such \(t_{i}=(g_{i},<_{i})\), let \(g_{i}=(V_{i},E_{i},src_{i},tar_{i},lab_{i},v_{i})\), where the node sets \(V_{i}\), \(i\in[k]\), are mutually disjoint, and similarly for the edge sets \(E_{i}\), \(i\in[k]\). The _top-concatenation_ of \(t_{1},\ldots,t_{k}\) with \(\sigma\), denoted by \(\sigma[t_{1},\ldots,t_{k}]\), is the tree obtained by attaching the trees \(t_{1},\ldots,t_{k}\) as children underneath a new root node with label \(\sigma\). Top-concatenation is analogously defined for single-rooted graphs, so we may write \(\sigma[g_{1},\ldots,g_{k}]\) without risk of confusion. In the case that the graphs are ordered, so are the edges \(e_{1},\ldots,e_{k}\) that attach the subgraphs \(g_{1},\ldots,g_{k}\); otherwise, they are unordered. Let \(X\) be a set of variables, such that \(X\cap\Sigma=\emptyset\). A _context_ is a tree \(c\in\Gamma_{\{x\}\cup\Sigma}\), for \(x\in X\), such that \(c\) contains exactly one occurrence of \(x\), and this occurrence is a leaf. Given such a context and a tree \(t\), we let \(c[t]\) denote the tree obtained from \(c\) by replacing the node labelled \(x\) with \(t\).