# Practical Access to Dynamic Programming on Tree Decompositions +
## 3 An Interface for Dynamic Programming on Tree Decompositions
### The Tree Automaton Perspective  
Classically, dynamic programs on tree decompositions are described in terms of tree automata [10]. Recall that, in a very nice tree decomposition, the tree \(T\) is rooted and binary; we assume that the children of \(T\) are ordered. The mapping \(\iota\) can then be seen as a function that maps the nodes of \(T\) to symbols from some alphabet \(\Sigma\). A naive approach to manage \(\iota\) would yield a huge alphabet (dependingon the size of the graph). We thus define the so-called _tree-index_, which is a map idx: \(V(G)\to\{0,\ldots,\operatorname{tw}(G)\}\) such that no two vertices that appear in the same bag share a common tree-index. The existence of such an index follows directly from the property that every vertex is forgotten exactly once: We can simply traverse \(T\) from the root to the leaves and assign a free index to a vertex \(V\) when it is forgotten, and release the used index once we reach an introduce bag for \(v\). The symbols of \(\Sigma\) then only contain the information for which tree-index there is a vertex in the bag. From a theoretician's perspective, this means that \(|\Sigma|\) depends only on the treewidth; from a programmer's perspective, the tree-index makes it much easier to manage data structures that are used by the dynamic program. **Definition 1** (Tree Automaton). : _A nondeterministic bottom-up tree automaton is a tuple \(A=(Q,\Sigma,\Delta,F)\), where \(Q\) is the set of states of the automaton, \(F\subseteq Q\) is the set of accepting states, \(\Sigma\) is an alphabet, and \(\Delta\subseteq(Q\cup\{\bot\})\times(Q\cup\{\bot\})\times\Sigma\times Q\) is a transition relation in which \(\bot\
ot\in Q\) is a special symbol to treat nodes with less than two children. The automaton is deterministic if, for every \(x,y\in Q\cup\{\bot\}\) and every \(\sigma\in\Sigma\), there is exactly one \(q\in Q\) with \((x,y,\sigma,q)\in\Delta\)._  
**Definition 2** (Computation of a Tree Automaton). : _The computation of a nondeterministic bottom-up tree automaton\(A=(Q,\Sigma,\Delta,F)\) on a labeled tree \((T,\iota)\) with \(\iota\colon V(T)\to\Sigma\) and root \(r\in V(T)\) is an assignment \(q\colon V(T)\to Q\) such that, for all \(n\in V(T)\), we have (1) \((q(x),q(y),\iota(n),q(n))\in\Delta\) if \(n\) has two children \(x\), \(y\); (2) \((q(x),\bot,\iota(n),q(n))\in\Delta\) or \((\bot,q(x),\iota(n),q(n))\in\Delta\) if \(n\) has one child \(x\); (3) \((\bot,\bot,\iota(n),q(n))\in\Delta\) if \(n\) is a leaf. The computation is accepting if \(q(r)\in F\)._  
Simulating Tree Automata  
A dynamic program for a decision problem can be formulated as a nondeterministic tree automaton that works on the decomposition--see the left side of Figure 1 for a detailed example. Observe that a nondeterministic tree automaton \(A\) will process a labeled tree \((T,\iota)\) with \(n\) nodes in time \(O(n)\). When we simulate such an automaton deterministically, one might think that a running time of the form \(O(|Q|\cdot n)\) is sufficient, as the automaton could be in any potential subset of the \(Q\) states at some node of the tree. However, there is a pitfall: for every node, we have to compute the set of potential states of the automaton depending on the sets of potential states of the children of that node, leading to a quadratic dependency on \(|Q|\). This can be avoided for transitions of the form \((\bot,\bot,\iota(x),p)\), \((q,\bot,\iota(x),p)\), and \((\bot,q,\iota(x),p)\), as we can collect potential successors of every state of the child and compute the new set of states in linear time with respect to the cardinality of the set. However, transitions of the form \((q_{i},q_{j},\iota(x),p)\) are difficult, as we now have to merge two sets of states. In detail, let \(x\) be a node with children \(y\) and \(z\) and let \(Q_{y}\) and \(Q_{z}\) be the set of potential states in which the automaton eventually is in at these nodes.