## 6 Conclusions  
In this paper, we presented a novel approach for ASP solving based on ideas from parameterized complexity. Our algorithms runs in linear time assuming bounded treewidth of the input program. Our solver applies DP in three traversals, thereby avoiding redundancies. Experimental results indicate that our ASP solver is competitive for certain classes of instances with small treewidth, where the latest version of the well-known solver Clasp hardly keeps up. \begin{table}
\begin{tabular}{l c c c c c c} \hline \hline \multirow{2}{*}{**Solver**} & \multirow{2}{*}{**Solved**} & \multicolumn{6}{c}{**Runtimes (Best) among Solved Instances**} & \multirow{2}{*}{**PAR2 Score**} \\ \cline{3-3} \cline{5-7}  & & **TD** & **3.I** & **3.II** & **3.III** & \(\Sigma\) \\ \hline Clasp 3.3.0 & 35 & - & - & - & - & 11,493.98 & 93,093.98 \\ DynASP2 & 13 & 7.96 (**0.2\%**) & - & - & - & 3978.29 & 138,378.29 \\ DynASP2.5 & 41 & 21.68 (**0.2\%**) & 130.10 (1.4\%) & 585.47 (6.2\%) & 8656.48 (92.2\%) & 9393.73 & 76,496.74 \\ “degraph\" & **45** & 408.72 (4.0\%) & 138.21 (1.4\%) & 595.58 (**5.8\%**) & 9033.70 (**88.8\%**) & 10,176.21 & **67,667.71** \\ “joinsize\" & 37 & 22.82 (0.3\%) & 120.19 (**1.3\%**) & 544.18 (6.1\%) & 8250.16 (92.3\%) & 8937.35 & 85,654.00 \\ \hline \multirow{2}{*}{Solver} & \multirow{2}{*}{Solved} & \multicolumn{6}{c}{Runtimes (median) among solved instances} & \multirow{2}{*}{PAR2 Score} \\ \cline{3-3} \cline{5-7}  & & TD & 3.I & 3.II & 3.III & \(\Sigma\) \\ \hline Clasp 3.3.0 & 34 & - & - & - & - & 11,688.58 & 94,523.53 \\ DynASP2 & 8 & 8.74 (**0.2\%**) & - & - & - & 4370.83 & 149,289.20 \\ DynASP2.5 & 32 & 21.91 (**0.2\%**) & 140.08 (**1.3\%**) & 685.15 (6.4\%) & 9878.67 (92.1\%) & 10,725.81 & 96,405.37 \\ “degraph\" & **38** & 473.12 (4.1\%) & 146.33 (**1.3\%**) & 661.00 (**5.8\%**) & 10,118.22 (**88.8\%**) & 11,398.67 & **81,425.39** \\ “joinsize\" & 32 & 25.47 (**0.2\%**) & 129.41 (**1.3\%**) & 596.62 (**5.8\%**) & 9538.77 (92.7\%) & 10,290.27 & 97,260.77 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The table illustrates detailed benchmark results, where data for the best possible among all five runs is depicted (top) and results for the median run are shown (bottom). All columns illustrate values in seconds, except the first two columns. Column “Solver” indicates a solving system or configuration and “Solved” refers to the number of solved instances. Then, columns “TD”, “3.I”, “3.II”, and “3.III” list the total runtime in seconds over all solved instances for computation involving obtaining TDs, Pass 3.I, Pass 3.II, and Pass 3.III, respectively. Column “\(\Sigma\)” refers to the total runtime in seconds over all solved instances. The last column depicts the PAR2 score over all instances, where timeouts are treated as two times the timeout (“PAR2 score”). Bold-face text indicates the best result in the corresponding column. An interesting question for future research is whether a linear amount of traversals (incremental dynamic programming) can improve the runtime behavior. It might also be worth investigating if more general parameters than treewidth can be used [42]. Furthermore, it might be interesting to apply high level approaches on dynamic programming that include the use of existing technology to answer set programming [43; 44] or whether such an approach pays off for other domains such as default logic [45], argumentation [46], or description logics [47]. Authors contributed equally. All authors have read and agreed to the published version of the manuscript. This work has been supported by the Vienna Science and Technology Fund (WWTF) project ICT19-065 and the Austrian Science Fund (FWF) projects P30168 and P32830. Not applicable. The source code of our solver is available at [[https://github.com/daajoe/dynasp/releases/tag/v2.5.0](https://github.com/daajoe/dynasp/releases/tag/v2.5.0)]([https://github.com/daajoe/dynasp/releases/tag/v2.5.0](https://github.com/daajoe/dynasp/releases/tag/v2.5.0)).