## 3 A Single Traversal DP Algorithm
#### An Algorithm on the Semi-Incidence Graph
Observe that the second row \(u_{6.2}=\langle M_{6.2},\sigma_{6.2}\rangle\in\tau_{6}\) does not have a \"successor row\" in \(\tau_{10}\), since \(r_{b}\
ot\in\sigma_{6.2}\). Intuitively, join node \(t_{34}\) joins only common witness sets in \(\tau_{17}\) and \(\tau_{33}\) with \(\chi(t_{17})=\chi(t_{33})=\chi(t_{34})\). In general, a join node marks rules satisfied, which are marked satisfied in at least one child (see L13-14). Figure 2: The tree decomposition \(\mathcal{T}\) of the semi-incidence graph \(S(P)\) for program \(P\) from Example 1 and Figure 1. Selected DP tables after \(\mathtt{DP_{MOD}}\). We explain details of the figure in Example 3. We assume again row numbers per table \(\tau_{t}\), i.e., \(u_{t,i}=\langle M_{t,i},\sigma_{t,i},\mathcal{C}_{t,i}\rangle\) is the \(i^{th}\)-row. Further, for each counter-witness \(\langle C_{t,i,j},\rho_{t,i,j}\rangle\in\mathcal{C}_{t,i}\), \(j\) marks its \"order\" (as depicted in Figure 3 (right)) in set \(\mathcal{C}_{t,i}\). **Example 4**. : _Again, we consider program \(P\) from Example 1, and \(\mathcal{T}=(\cdot,\chi)\) of Figure 3 as well as tables \(\tau_{1}\), \(\ldots\), \(\tau_{34}\) of Figure 3 (right) using \(\mathtt{DP}_{\mathsf{SINC}}\). We only discuss certain tables. Table \(\tau_{1}=\{\langle\emptyset,\emptyset,\emptyset\rangle\}\) as \(\mathtt{type}(t_{1})=\) leaf. Node \(t_{2}\) introduces atom \(e_{ab}\), resulting in table \(\{\langle\{e_{ab}\},\emptyset,\{(\emptyset,\emptyset)\}\rangle,\langle \emptyset,\emptyset\rangle\}\) (compare to Algorithm 2 L3-5). Then, node \(t_{3}\) introduces rule \(t_{ab}\), which is forgotten in node \(t_{4}\). Note that \(C_{3.1.1}=\langle\emptyset,\emptyset\rangle\in\mathcal{C}_{3.1.1}\) does not have a \"successor row\" in table \(\tau_{4}\) since \(r_{ab}\) is not satisfied (see L11 and Definition 2). Table \(\tau_{6}\) is then the result of a chain of introduce nodes, and contains for each witness set \(M_{6,i}\) every possible counter-witness set \(\mathsf{C}_{6,i,j}\) with \(\mathsf{C}_{6,i,j}\subsetneq M_{6,i}\). We now discuss table \(\tau_{12}\), intuitively containing (a projection of) (counter-)witnesses of \(\tau_{10}\), which satisfy rule \(r_{b}\) after introducing rule \(r_{c1}\). Observe that there is no succeeding witness set for \(M_{6.2}=\{e_{ab}\}\) in \(\tau_{10}\) (nor \(\tau_{12}\)), since \(e_{ab}\in M_{6.2}\), but \(a_{b}\
ot\in M_{6.2}\) (required to satisfy \(r_{b}\)). Rows \(u_{12,1},u_{12,4}\) form successors of \(u_{6,3}\), while rows \(u_{12,2},u_{12,5}\) succeed \(u_{6,1}\), since counter-witness set \(C_{6.1.1}\) has no succeeding row in \(\tau_{10}\) because it does not satisfy \(r_{b}\). Remaining rows \(u_{123}\), \(u_{12,6}\) have \"origin\" \(u_{6,4}\) in \(\tau_{6}\)._

## 4 DynASP2.5: Towards a III Traversal DP Algorithm

The classical DP algorithm \(\mathtt{DP}_{\mathsf{SINC}}\) (Step 3 of Figure 4) follows a single traversal approach. It computes both witnesses and counter-witnesses by traversing the given TD exactly once. In particular, it stores exhaustively all potential counter-witnesses, even those counter-witnesses where the witnesses in the table of a node cannot be extended in the parent node. In addition, there can be a high number of duplicates among the counter-witnesses, which are stored repeatedly. Figure 3: Extends Figure 2. The figure illustrates a tree decomposition \(\mathcal{T}\) of the semi-incidence graph \(S(P)\) for program \(P\) from Example 1 (**center**). Selected DP tables after \(\mathtt{DP}_{\mathsf{MOD}}\) (**left**) and after \(\mathtt{DP}_{\mathsf{SINC}}\) (**right**) for nice tree decomposition \(\mathcal{T}\). We explain details of the figure in Example 4. In this section, we propose a multi-traversal approach (\(\mathsf{M\text{-}DP_{SINC}}\)) for DP on TDs and a new implementation (DynASP2.5), which fruitfully adapts and extends ideas from a different domain [17].