# Parsing Unranked Tree Languages, Folded Once +
## 4 Unfolding Folded Trees
### Reassembly Sequences by Vector Addition Systems  
To prove Theorem 1, we rely on the signatures to tell us what multisets of states each tree fragment can \"consume\", and what state it then \"produces\". Finding a way of puzzling the fragments together consistently is a combinatorial problem which we will solve by reducing it to reachability in a restricted form of vector addition systems [25] (the restrictions are key as vector addition systems are in general very powerful [26]). We next present these systems and prove the relevant complexity bound. We then explain the reduction in the proof of Theorem 1. For vectors \(u\) and \(v\), let \((u;v)\) denote their concatenation. Let \(0\) denote the set of all vectors of zeros, and for all \(k\geq 1\), let \(\mathbb{1}_{[k]}=\{(z_{1};1;z_{2})\mid z_{1},z_{2}\in 0,|z_{1}|=k-1\}\), i.e., the unit vectors with a \(1\) in position \(k\). Let \(1=\cup_{k\geq 1}\mathbb{1}_{[k]}\); i.e., all unit vectors. We may treat \(0\) and \(1\) as vectors when the length is implied by context. For a vector \(s\), we write \(s\geq 0\) to indicate that \(s\) is pointwise greater than or equal to \(0\), i.e., that every element of \(s\) is nonnegative. **Definition 6**. : _A Vector Addition System of dimension \(k\in\mathbb{N}\) (a \(k\)-VAS) is a finite set \(V=\{(p,p^{\prime})\mid p\in\{-v\mid v\in\mathbb{N}^{k}\},p^{\prime}\in \mathbb{N}^{k}\}\). We call these the operations. An operation sequence in \(V\) is denoted \(s_{0}\rightarrow_{(p_{1},p_{1}^{\prime})}s_{1}\rightarrow_{(p_{2},p_{2}^{ \prime})}\cdots\rightarrow_{(p_{n},p_{n}^{\prime})}s_{n}\) for \(s_{0},\ldots,s_{n}\in\mathbb{N}^{k}\), and for each \(1\leq i\leq n\)_  
\[1.\ (p_{i},p_{i}^{\prime})\in V,\qquad 2.\,s_{i-1}+p_{i}\geq 0,\qquad\text{and}, \qquad 3.\,s_{i}=s_{i-1}+p_{i}+p_{i}^{\prime}\enspace.\]  
_A vector \(s_{n}\) is reachable from \(s_{0}\) if and only if such an operation sequence exists._  
_For any \(k,l\in\mathbb{N}\), we call a \((k+l)\)-VAS \(V\) a \((k,l)\)-VAS to differentiate the first \(k\) elements of the vectors from the rest, writing \(((u;v),(u^{\prime};v^{\prime}))\in V\) to signify that \(|u|=|u^{\prime}|=k\) and \(|v|=|v^{\prime}|=l\)._  
While we define reachability in terms of going from a vector \(s\) to a vector \(t\), we are primarily interested in the special case of \(0\) being reachable, since the numbers will represent tree fragments, all of which must be used. **Definition 7**. : _A \((k,l)\)-VAS \(V\) is metered if all \(((s;b),(s^{\prime};b^{\prime}))\in V\) have \(s,b\in-1\) and \(b^{\prime}\in 0\)._That is, in a metered \((k,l)\)-VAS, every operation takes precisely one unit from each of the two parts of the vector, and never adds anything to the second part. We will use the first part, the \(s\) vector, to represent a _multiset of states_, while the second, the \(b\) vector, represents a _budget_. We will informally refer to the vectors accordingly where it makes things more intuitive. This bounded budget then limits the computation in a way similar to a \(k\)-bounded Petri net [27]. **Definition 8**. : _For a \((k,l)\)-VAS \(V\) an operation sequence \((s_{0};b_{0})\rightarrow_{p_{1}}\cdots\rightarrow_{p_{n}}(s_{n};b_{n})\) visits a position \(i\in[k]\) if at least one vector \(s\in\{s_{0},\ldots,s_{n}\}\) is nonzero in position \(i\). The set \(I\subseteq[k]\) is visited if all elements are visited._  
Visits only concern the first (state) part of the vector, which makes sense for a metered VAS, as a position in the second part is visited iff it is visited in \(b_{0}\). We will use _visits_ to correspond to uses of states in a run of an automaton over a tree. We next show that if there exists an operation sequence which visits a set \(I\) starting from a vector \(v_{0}\), then there is a _short subsequence_ that does the same. **Lemma 1**.