## 3 A Single Traversal DP Algorithm
#### An Algorithm on the Semi-Incidence Graph
Then, we construct the following formulas:

\[\{(\hat{C}^{\prime}\cup\hat{M}^{\prime\prime},\hat{\sigma}^{ \prime\prime})\mid(\hat{C}^{\prime},\hat{\sigma}^{\prime})\in\hat{C}^{\prime},\hat{C}^{\prime}\cap\mathrm{at}_{t}=\hat{M}^{\prime\prime}\cap\mathrm{at}_{t}\}\cup\]3 for \[\{(\hat{C}^{\prime}\cup\hat{M}^{\prime\prime},\hat{\sigma}^{ \prime\prime})\mid(\hat{C}^{\prime},\hat{\sigma}^{\prime})\in\hat{C}^{\prime},\hat{C}^{\prime}\cap\mathrm{at}_{t}=\hat{M}^{\prime\prime}\cap\mathrm{at}_{t}\}\cup\]4 \[\{(\hat{C}^{\prime}\cup\hat{M}^{\prime\prime},\hat{\sigma}^{ \prime\prime})\mid(\hat{C}^{\prime},\hat{\sigma}^{\prime})\in\hat{C}^{\prime},\hat{C}^{\prime}\cap\mathrm{at}_{t}=\hat{M}^{\prime\prime}\cap\mathrm{at}_{t}\}\cup\]5 for \[\{(\hat{C}^{\prime}\cup\hat{M}^{\prime\prime},\hat{\sigma}^{ \prime\prime})\mid(\hat{C}^{\prime},\hat{\sigma}^{\prime})\in\hat{C}^{\prime},\hat{C}^{\prime}\cap\mathrm{at}_{t}=\hat{M}^{\prime\prime}\cap\mathrm{at}_{t}\}\cup\]6 (2) \[\{(\hat{C}^{\prime}\cup\hat{M}^{\prime\prime},\hat{\sigma}^{ \prime\prime})\mid(\hat{C}^{\prime},\hat{\sigma}^{\prime})\in\hat{C}^{\prime},\hat{C}^{\prime}\cap\mathrm{at}_{t}=\hat{M}^{\prime\prime}\cap\mathrm{at}_{t}\}\cup\]7 for \[\{(\hat{C}^{\prime}\cup\hat{M}^{\prime\prime},\hat{\sigma}^{ \prime\prime})\mid(\hat{C}^{\prime},\hat{\sigma}^{\prime})\in\hat{C}^{\prime},\hat{C}^{\prime}\cap\mathrm{at}_{t}=\hat{M}^{\prime\prime}\cap\mathrm{at}_{t}\}\cup\]8 (3) \[\{(\hat{C}^{\prime}\cup\hat{M}^{\prime\prime},\hat{\sigma}^{ \prime\prime})\mid(\hat{C}^{\prime},\hat{\sigma}^{\prime})\in\hat{C}^{\prime},\hat{C}^{\prime}\cap\mathrm{at}_{t}=\hat{M}^{\prime\prime}\cap\mathrm{at}_{t}\}\cup\]9 (4) \[\{(\hat{M}^{\prime}\cup\hat{C}^{\prime\prime},\hat{\sigma}^{ \prime\prime})\mid(\hat{C}^{\prime\prime},\hat{\sigma}^{\prime\prime})\in\hat{C} ^{\prime\prime},\hat{M}^{\prime}\cap\mathrm{at}_{t}=\hat{C}^{\prime\prime}\cap \mathrm{at}_{t}\}.\]0

Next, we show that \(M\) is an answer set of \(P\) if and only if \(M\cup([M\cap B^{-}_{P}])^{\prime}\cup\{sol\}\) is a subset-minimal model of \(F\). (\(\Rightarrow\)): Let \(M\) be an answer set of \(P\). We transform \(M\) into \(Y:=M\cup([M\cap B^{-}_{P}])^{\prime}\cup\{sol\}\). Observe that \(Y\) satisfies all subformulas of \(F\) and therefore \(Y\vDash F\). It remains to show that \(Y\) is a minimal model of \(F\). Assume towards a contradiction that \(Y\) is not a minimal model. Hence, there exists \(X\) with \(X\subsetneq Y\). We distinguish the following cases:

1. \(sol\in X\): By construction of \(F\) we have \(X\vDash a^{\prime}\leftrightarrow a\) for any \(a^{\prime}\in(B^{-}_{P})^{\prime}\), which implies that \(X\cap\mathrm{at}(P)\vDash P^{M}\). However, this contradicts our assumption that \(M\) is an answer set of \(P\). 2. \(sol\
ot\in X\): By construction of \(F\) there is at least one atom \(a\in B^{-}_{P}\) with \(a^{\prime}\in X\), but \(a\
ot\in X\). Consequently, \(X\cap\mathrm{at}(P)\vDash P^{M}\). This contradicts again that \(M\) is an answer set of \(P\). (\(\Leftarrow\)): Given a formula \(F\) that has been constructed from a program \(P\) as given above. Then, let \(Y\) be a subset-minimal model of \(F\) such that \(sol\in Y\). By construction we have for every \(a^{\prime}\in Y\cap(B^{-}_{P})^{\prime}\) that \(a\in Y\). Hence, we let \(M=\mathrm{at}(P)\cap Y\). Observe that \(M\) satisfies every rule \(r\in P\) according to (A1) and is in consequence a model of \(P\). It remains to show that \(M\) is indeed an answer set. Assume towards a contradiction that \(M\) is not an answer set. Then there exists a model \(N\subsetneq M\) of the reduct \(P^{M}\). We distinguish the following cases:

1. \(N\) is not a model of \(P\): We construct \(X:=N\cup[Y\cap(B^{-}_{P})^{\prime}]\) and show that \(X\) is indeed a model of \(F\). For this, for every \(r\in P\) where \(B^{-}(r)\cap M\
eq\emptyset\) we have \(X\vDash F^{\mathrm{r}}(r)\), since \((Y\cap(B^{-}_{P})^{\prime})\subseteq X\) by definition of \(X\).