Non-deterministic Approximation Operators: Ultimate Operators, Semi-equilibrium Semantics, and Aggregates

Abstract

Approximation fixpoint theory (AFT) is an abstract and general algebraic framework for studying the semantics of non-monotonic logics. In recent work, AFT was generalized to non-deterministic operators, that is, operators whose range are sets of elements rather than single elements. In this paper, we make three further contributions to non-deterministic AFT: (1) we define and study ultimate approximations of non-deterministic operators, (2) we give an algebraic formulation of the semi-equilibrium semantics by Amendola et al., and (3) we generalize the characterizations of disjunctive logic programs to disjunctive logic programs with aggregates.

1 Introduction

Knowledge representation and reasoning (KRR), by its very nature, is concerned with the study of a wide variety of languages and formalisms. In view of this, unifying frameworks that allow for the language-independent study of aspects of KRR is essential. One framework with strong unifying potential is approximation fixpoint theory (AFT) (Denecker et al. 2000), a purely algebraic theory which was shown to unify the semantics of, among others, logic programming default logic and autoepistemic logic. The central objects of study of AFT are (approximating) operators and their fixpoints. For logic programming for instance, it was shown that Fitting’s three-valued immediate consequence operator is an approximating operator of Van Emden and Kowalski’s two-valued immediate consequence operator, and that all major semantics of (normal) logic programming can be derived directly from this approximating operator. Moreover, this observation does not only hold for logic programming: also for a wide variety of other domains, it is straightforward how to derive an approximating operator, and the major semantics can be recovered from that approximator using purely algebraic means (an overview is given by Heyninck et al. 2022). This has in turn inspired others to define the semantics of non-monotonic formalisms directly using AFT (Bogaerts 2019), putting AFT forward not only as a framework to study existing semantics but also as a framework to define them. The advantage is that AFT-based semantics are guaranteed to follow well-established principles, such as groundedness (Bogaerts 2015). Moreover, it is often easier to define a semantic operator than to define the semantics from scratch.

Recently, AFT was generalized to also capture non-deterministic operators (Heyninck et al. 2022) which allow for different options or choices in their output. A prime example of the occurrence of non-determinism in KRR is disjunctive logic programming, and it was indeed shown that many semantics of disjunctive logic programming (specifically the weakly supported, (partial) stable, and well-founded semantics (Alcântara et al. 2005) are captured by non-deterministic AFT. In this paper, we make further contributions to the study of non-deterministic AFT, with a particular emphasis on disjunctive logic programs. On the one hand, (in Section 3) we deepen the theory of non-deterministics AFT by investigating so-called ultimate semantics. For standard AFT, Denecker et al. (2002) have shown that with every two-valued operator, we can uniquely associate a most-precise approximator called the ultimate approximator. When defining semantics of new formalisms, this even takes the need of defining an approximator away, since it suffices to define an exact operator and its ultimate approximator comes for free. ¹ Our first contribution is to show how ultimate approximations can be obtained for non-deterministic AFT, which we later illustrate using disjunctive logic programs with aggregates. This means we give the first constructive method for obtaining non-deterministic approximation operators. On the other hand, we also apply non-deterministic AFT to two areas that have thus far been out of reach of AFT. In Section 4, we use it to define an algebraic generalization of the semi-equilibrium semantics, a semantics originally formulated for disjunctive logic programs (Amendola et al. 2016) but now, thanks to our results, available to any operator-based semantics. In Section 5, we apply the theory of non-deterministic AFT to disjunctive logic programs with aggregates in the body, giving rise to a family of semantics for such programs.

2 Background and preliminaries

In this section, we recall disjunctive logic programming (Section 2.1), AFT for deterministic operators (Section 2.2), and non-deterministic operators (Section 2.3).

2.1 Disjunctive logic programming

In what follows we consider a propositional ² language ${\mathfrak L}$ , whose atomic formulas are denoted by p,q,r (possibly indexed), and that contains the propositional constants ${\sf T}$ (representing truth), ${\sf F}$ (falsity), ${\sf U}$ (unknown), and ${\sf C}$ (contradictory information). The connectives in ${\mathfrak L}$ include negation $\neg$ , conjunction $\wedge$ , disjunction $\vee$ , and implication $\leftarrow$ . Formulas are denoted by $\phi$ , $\psi$ , $\delta$ (again, possibly indexed). Logic programs in ${\mathfrak L}$ may be divided to different kinds as follows: a (propositional) disjunctive logic program ${\cal P}$ in ${\mathfrak L}$ (a dlp in short) is a finite set of rules of the form $\bigvee_{i=1}^n p_i~\leftarrow~\psi$ , where the head $\bigvee_{i=1}^n p_i$ is a non-empty disjunction of atoms, and the body $\psi$ is a formula not containing $\leftarrow$ . A rule is called normal (nlp), if its body is a conjunction of literals (i.e., atomic formulas or negated atoms), and its head is atomic. A rule is disjunctively normal if its body is a conjunction of literals and its head is a non-empty disjunction of atoms. We will use these denominations for programs if all rules in the program satisfy the denomination, for example, a program is normal if all its rules are normal. The set of atoms occurring in $\mathcal{P}$ is denoted ${\cal A}_{\cal P}$ .

The semantics of dlps are given in terms of four-valued interpretations. A four-valued interpretation of a program ${\cal P}$ is a pair (x,y), where $x \subseteq {\cal A}_{\cal P}$ is the set of the atoms that are assigned a value in $\{{\sf T},{\sf C}\}$ and $y \subseteq {\cal A}_{\cal P}$ is the set of atoms assigned a value in $\{{\sf T},{\sf U}\}$ . We define $-{\sf T}={\sf F}$ , $-{\sf F}={\sf T}$ and ${\sf X}=-{\sf X}$ for ${\sf X}={\sf C},{\sf U}$ . Truth assignments to complex formulas are as follows:

A four-valued interpretation of the form (x,x) may be associated with a two-valued (or total) interpretation x. (x,y) is a three-valued (or consistent) interpretation, if $x \subseteq y$ . Interpretations are compared by two-order relations which form a pointwise extension of the structure ${\cal FOUR}$ consisting of ${\sf T}, {\sf F},{\sf C}$ , and ${\sf U}$ with ${\sf U}<_i {\sf F},{\sf T}<_i {\sf C}$ and ${\sf F}<_t {\sf C},{\sf U}<_t {\sf T}$ . The pointwise extension of these orders corresponds to the information order, which is equivalently defined as $(x,y)\leq_i (w,z)$ iff $x\subseteq w$ and $z\subseteq y$ , and the truth order, where $(x,y)\leq_t (w,z)$ iff $x\subseteq w$ and $y\subseteq z$ .

The immediate consequence operator for normal programs (van Emden and Kowalski 1976) is extended to dlps as follows:

Definition 1 (Immediate Consquence operator for dlps)

Given a dlp ${\cal P}$ and a two-valued interpretation x, we define: (1) $\mathit{HD}_{\cal P}(x)=\{\Delta\mid \bigvee\!\Delta\leftarrow \psi \in{\cal P} \text{ and } (x,x)(\psi) = {\sf T}\}$ ; and (2) $\mathit{IC}_{\cal P}(x)=\{y\subseteq \:\bigcup\!\mathit{HD}_{\cal P}(x) \mid \forall \Delta \in \mathit{HD}_{\cal P}(x), y \cap \Delta \neq \emptyset \}$ .

Thus, $\mathit{IC}_{\cal P}(x)$ consists of sets of atoms that occur in activated rule heads, each set contains at least one representative from every disjuncts of a rule in ${\cal P}$ whose body is x-satisfied. Denoting by $\wp({\cal S})$ , the powerset of ${\cal S}$ , $\mathit{IC}_{\cal P}$ is an operator on the lattice ${\langle \wp({\cal A}_{\cal P}),\subseteq \rangle}$ .³

Given a dlp ${\cal P}$ a consistent interpretation (x,y) is a (three-valued) model of ${\cal P}$ , if for every $\phi\leftarrow \psi \in {\cal P}$ , $(x,y)(\phi)\geq_t (x,y)(\psi)$ . The GL-transformation $\frac{\cal P}{(x,y)}$ of a disjunctively normal dlp ${\cal P}$ with respect to a consistent (x,y) is the positive program obtained by replacing in every rule in ${\cal P}$ of the form $p_1\lor\ldots\lor p_n \leftarrow \bigwedge_{i=1}^m q_i\land \bigwedge_{j=1}^n \lnot r_j$ a negated literal $\lnot r_i$ ( $1\leq i\leq k$ ) by $(x,y)(\lnot r_i)$ . (x,y) is a three-valued stable model of ${\cal P}$ iff it is a $\leq_t$ -minimal model of $\frac{{\cal P}}{(x,y)}$ . ⁴

2.2 Approximation fixpoint theory

We now recall basic notions from AFT, as described by Denecker et al. (2000). We restrict ourselves here to the necessary formal details and refer to more detailed introductions by Denecker et al. (2000) and Bogaerts (2015) for more informal details. AFT introduces constructive techniques for approximating the fixpoints of an operator O over a lattice $L= {\langle {\cal L},\leq \rangle}$ .⁵ Approximations are pairs of elements (x,y). Thus, given a lattice $L = {\langle {\cal L},\leq \rangle}$ , the induced bilattice is the structure $L^2 ={\langle {\cal L}^2,\leq_i,\leq_t \rangle}$ , in which ${\cal L}^2 = {\cal L} \times {\cal L}$ , and for every $x_1,y_1,x_2,y_2 \in {\cal L }$ , $(x_1,y_1) \leq_i (x_2,y_2)$ if $x_1 \leq x_2$ and $y_1 \geq y_2$ , and $(x_1,y_1) \leq_t (x_2,y_2)$ if $x_1 \leq x_2$ and $y_1 \leq y_2$ . ⁶

An approximating operator ${\cal O}:{\cal L}^2\rightarrow {\cal L}^2$ of an operator $O:{\cal L}\rightarrow {\cal L}$ is an operator that maps every approximation (x,y) of an element z to an approximation (x’,y’) of another element O(z), thus approximating the behavior of the approximated operator O. In more details, an operator ${\cal O}:{\cal L}^2\rightarrow {\cal L}^2$ is $\leq_i$ -monotonic, if when $(x_1,y_1)\leq_i(x_2,y_2)$ , also ${\cal O}(x_1,y_1)\leq_i {\cal O}(x_2,y_2)$ ; ${\cal O}$ is approximating, if it is $\leq_i$ -monotonic and for any $x\in {\cal L}$ , ${\cal O}_l(x,x) = {\cal O}_u(x,x)$ .⁷ ${\cal O}$ approximates of $O:{\cal L}\rightarrow {\cal L}$ , if it is $\leq_i$ -monotonic and ${\cal O}(x,x) = (O(x), O(x))$ (for every $x\in {\cal L}$ ). Finally, for a complete lattice L, let ${\cal O}:{\cal L}^2 \rightarrow {\cal L}^2$ be an approximating operator. We denote ${\cal O}_{l}(\cdot,y) = \lambda x.{\cal O}_{l}(x,y)$ and similarly for ${\cal O}_{u}$ . The stable operator for ${\cal O}$ is then defined as $S({\cal O})(x,y)=(lfp({\cal O}_l(.,y)),lfp({\cal O}_u(x,.))$ , where lfp(O) denotes the least fixpoint of an operator O.

Approximating operators induce a family of fixpoint semantics. Given a complete lattice $L = {\langle {\cal L},\leq \rangle}$ and an approximating operator ${\cal O}:{\cal L}^2 \rightarrow {\cal L}^2$ , (x,y) is a Kripke–Kleene fixpoint of ${\cal O}$ if $(x,y) =lfp_{\leq_i}({\cal O}(x,y))$ ; (x,y) is a three-valued stable fixpoint of ${\cal O}$ if $(x,y)= S({\cal O})(x,y) $ ; (x,y) is a two-valued stable fixpoints of ${\cal O}$ if $x=y$ and $(x,x)= S({\cal O})(x,x)$ ; (x,y) is the well-founded fixpoint of ${\cal O}$ if it is the $\leq_i$ -minimal (three-valued) stable fixpoint of ${\cal O}$ .

2.3 Non-deterministic AFT

AFT was generalized to non-deterministic operators, that is, operators which map elements of a lattice to a set of elements of that lattice (like the operator $\mathit{IC}_{\cal P}$ for dlps) by Heyninck et al. (2022). We recall the necessary details, referring to the original paper for more details and explanations.

A non-deterministic operator on ${\cal L}$ is a function $O : {\cal L}\rightarrow \wp({\cal L}) \setminus \{\emptyset\}$ . For example, the operator $\mathit{IC}_{\cal P}$ from Definition 1 is a non-deterministic operator on the lattice ${\langle \wp({\cal A}_{\cal P}),\subseteq \rangle}$ .

As the ranges of non-deterministic operators are sets of lattice elements, one needs a way to compare them, such as the Smyth order and the Hoare order. Let $L = {\langle {\cal L},\leq \rangle}$ be a lattice, and let $X,Y \in \wp({\cal L})$ . Then, $X \preceq^S_L Y$ if for every $y\in Y$ there is an $x\in X$ such that $x\leq y$ ; and $X \preceq^H_L Y$ if for every $x\in X$ there is a $y\in Y$ such that $x\leq y$ . Given some $X_1,X_2,Y_1,Y_2\subseteq {\cal L}$ , $X_1\times Y_1 \preceq^A_i X_2\times Y_2$ iff $X_1\preceq^S_L X_2$ and $Y_2\preceq^H_L Y_1$ . Let $L={\langle {\cal L},\leq \rangle}$ be a lattice. Given an operator ${\cal O}:{\cal L}^2\rightarrow {\cal L}^2$ , we denote by ${\cal O}_l$ the operator defined by ${\cal O}_l(x,y)={\cal O}(x,y)_1$ , and similarly for ${\cal O}_u(x,y)={\cal O}(x,y)_2$ . An operator ${\cal O}:{\cal L}^2\rightarrow \wp({\cal L}){\setminus\emptyset}\times \wp({\cal L}){\setminus\emptyset}$ is called a non-deterministic approximating operator (ndao, for short), if it is $\preceq^A_i$ -monotonic (i.e., $(x_1,y_1)\leq_i (x_2,y_2)$ implies ${\cal O}(x_1,y_1)\preceq^A_i {\cal O}(x_2,y_2)$ ) and is exact (i.e., for every $x\in {\cal L}$ , ${\cal O}(x,x)={\cal O}_l(x,x)\times {\cal O}_{l}(x,x)$ ). We restrict ourselves to ndaos ranging over consistent pairs (x,y).

We finally define the stable operator (given an ndao ${\cal O}$ ) as follows. The complete lower stable operator is defined by (for any $y\in {\cal L}$ ) $C({\cal O}_l)(y) \ = \{x \in {\cal L}\mid x\in {\cal O}_l(x,y) \mbox{ and }\lnot \exists x'< x: x'\in {\cal O}_l(x',y)\}$ . The complete upper stable operator is defined by (for any $x\in {\cal L}$ ) $C({\cal O}_u)(x) \ =\ \{y \in {\cal L}\mid y\in {\cal O}_u(x,y) \mbox{ and }\lnot \exists y'<y: y' \in {\cal O}_u(x,y')\}$ . The stable operator: $S({\cal O})(x,y)=C({\cal O}_l)(y)\times C({\cal O}_u)(x)$ . (x,y) is a stable fixpoint of ${\cal O}$ if $(x,y)\in S({\cal O})(x,y)$ .⁸

Other semantics, for example, the well-founded state and the Kripke–Kleene fixpoints and state are defined by Heyninck et al. (2022) and can be immediately obtained once an ndao is formulated.

Example 1 An example of an ndao approximating $\mathit{IC}_{\cal P}$ (Definition 1) is defined as follows (given a dlp ${\cal P}$ and an interpretation (x,y)): $\mathcal{HD}^l_{\cal P}(x,y) = \{ \Delta \mid \bigvee\!\Delta \leftarrow \phi\in {\cal P}, (x,y)(\phi)\geq_t {\sf C}\}$ , $\mathcal{HD}^u_{\cal P}(x,y) = \{ \Delta \mid \bigvee\!\Delta \leftarrow \phi\in {\cal P}, (x,y)(\phi)\geq_t {\sf U}\}$ , ${\cal IC}^\dagger_{\cal P}(x,y)=\{x_1\subseteq \bigcup\mathcal{HD}^\dagger_{\cal P}(x,y) \mid \forall \Delta\in \mathcal{HD}^\dagger_{\cal P}(x,y), \ x_1 \cap \Delta \neq \emptyset \}$ (for $\dagger\in \{l,u\}$ ), and ${\cal IC}_{\cal P}(x,y)=({\cal IC}^l_{\cal P}(x,y), {\cal IC}^u_{\cal P}(x,y))$ .

Consider the following dlp: ${\cal P}=\{ p\lor q\leftarrow\lnot q\}$ . The operator ${\cal IC}^l_{\cal P}$ behaves as follows: 12pt

• • For any interpretation (x,y) for which $q\in x$ , $\mathcal{HD}^l_{\cal P}(x,y)=\emptyset$ and thus ${\cal IC}^l_{\cal P}(x,y)=\{\emptyset\}$ .

• • For any interpretation (x,y) for which $q\not\in x$ , $\mathcal{HD}^l_{\cal P}(x,y)=\{\{p,q\}\}$ and thus ${\cal IC}^l_{\cal P}(x,y)=\{\{p\},\{q\},\{p,q\}\}$ .

Since ${\cal IC}_{\cal P}^l(x,y)={\cal IC}_{\cal P}^u(y,x)$ (see Heyninck et al. 2022, Lemma 1), ${\cal IC}_{\cal P}$ behaves as follows:

• • For any (x,y) with $q\not\in x$ and $q\not\in y$ , ${\cal IC}_{\cal P}(x,y)=\{\{p\},\{q\},\{p,q\}\}\times \{\{p\},\{q\},\{p,q\}\}$ ,

• • For any (x,y) with $q\not\in x$ and $q\in y$ , ${\cal IC}_{\cal P}(x,y)=\{\emptyset\}\times \{\{\{p\},\{q\},\{p,q\}\}$ ,

• • For any (x,y) with $q\in x$ and $q\not\in y$ , ${\cal IC}_{\cal P}(x,y)=\{\{p\},\{q\},\{p,q\}\}\times \{\emptyset\}$ , and

• • For any (x,y) with $q\in x$ and $q\in y$ , ${\cal IC}_{\cal P}(x,y)=\{(\emptyset,\emptyset)\}$ .

We see, for example, that $C({\cal IC}^l_{\cal P})(\{p\})=\{\{p\},\{q\}\}$ and thus $(\{p\},\{p\})$ is a stable fixpoint of ${\cal IC}_{\cal P}$ . $(\emptyset,\{q\})$ is the second stable fixpoint of ${\cal IC}_{\cal P}$ . $(\emptyset,\{p,q\})$ is a fixpoint of ${\cal IC}_{\cal P}$ that is not stable.

In general, (total) stable fixpoints of ${\cal IC}_{\cal P}$ correspond to (total) stable models of ${\cal P}$ , and weakly supported models of ${\cal IC}_{\cal P}$ correspond to fixpoints of ${\cal IC}_{\cal P}$ . (Heyninck et al. 2022).

3 Ultimate operators

AFT assumes an approximation operator but does not specify how to construct it. In the literature, one finds various ways to construct a deterministic approximation operator ${\cal O}$ that approximates a deterministic operator O. Of particular interest is the ultimate operator (Denecker et al. 2002), which is the most precise approximation operator. In this section, we show that non-deterministic AFT admits an ultimate operator, which is, however, different from the ultimate operator for deterministic AFT.

We first recall that for a deterministic operator $O: {\cal L}\rightarrow {\cal L}$ , the ultimate approximation ${\cal O}^u$ is defined by Denecker et al. (2002) as follows:⁹

\[{\cal O}^{\sf DMT^d}(x,y)=(\sqcap O[x,y], \sqcup O[x,y])\]

¹⁰ Where $O[x,y]:=\{O(z)\mid x\leq z\leq y\}$ . This operator is shown to be the most precise operator approximating an operator O (Denecker et al. 2002). In more detail, for any (deterministic) approximation operator ${\cal O}$ approximating O, and any consistent (x,y), ${\cal O}(x,y)<_i {\cal O}^{\sf DMT^d}(x,y)$ .

The ultimate approximator for $\mathit{IC}_{\cal P}$ for non-disjunctive logic programs ${\cal P}$ looks as follows:

Definition 2 Given a normal logic program ${\cal P}$ , we let: ${\cal IC}_{\cal P}^{{\sf DMT^d}}(x,y)=({\cal IC}_{\cal P}^{{\sf DMT^d},l}(x,y),\:{\cal IC}_{\cal P}^{{\sf DM^d},u}(x,y))$ with: ${\cal IC}_{\cal P}^{{\sf DMT^d},l}(x,y)=\bigcap_{x\subseteq z\subseteq y} \{\alpha\mid \alpha\leftarrow \phi\in {\cal P} \mbox{ and }z(\phi)={\sf T} \}$ , and ${\cal IC}_{\cal P}^{{\sf DMT^d},u}(x,y)=\bigcup_{x\subseteq z\subseteq y} \{\alpha\mid \alpha\leftarrow \phi\in {\cal P} \mbox{ and }z(\phi)={\sf T}\}$ .

In this section, we define the ultimate semantics for the non-deterministic operators. In more detail, we constructively define an approximation operator that is most precise and has non-empty upper and lower bounds. Its construction is based on the following idea: we are looking for an operator ${\cal O}^{\cal U}$ s.t. for any ndao ${\cal O}$ that approximates O, ${\cal O}_l(x,y)\preceq^S_L {\cal O}_l^{\cal U}(x,y)$ (and similarly for the upper bound). As we know that ${\cal O}_l(x,y)\preceq^S_L O(z)$ for any $x\leq z\leq y$ , we can obtain ${\cal O}_l^{\cal U}$ by simply gathering all applications of O to elements of the interval [x,y], that is, we define

\[ {\cal O}^{{\cal U}}_l(x,y)=\bigcup_{x\leq z\leq y} O(z)\]

The upper bound can be defined in the same way as the lower bound. Altogether, we obtain

\[{\cal O}^{\cal U}(x,y)= {\cal O}^{\cal U}_l(x,y)\times {\cal O}^{\cal U}_l(x,y)\]

The following example illustrates this definition for normal logic programs:

Example 2 Let ${\cal P}=\{q\leftarrow \lnot p; p\leftarrow p\}$ . Then $IC_{\cal P}(\emptyset)=IC_{\cal P}(\{q\})=\{q\}$ and $IC_{\cal P}(\{p\})=IC_{\cal P}(\{p,q\})=\{p\}$ . Therefore, ${\cal IC}^{\cal U}_{\cal P}(\emptyset,\{p,q\})=\{\{p\},\{q\}\}\times \{\{p\},\{q\}\}$ whereas ${\cal IC}^{\cal U}_{\cal P}(\emptyset,\{q\})=\{\{q\}\}\times\{\{q\}\}$ .

The ultimate approximation is the most precise ndao approximating the operator O:

Proposition 1 Let a non-deterministic operator O over a lattice $\langle {\cal L},\leq\rangle$ be given. Then ${\cal O}^{\cal U}$ is an ndao that approximates O. Furthermore, for any ndao ${\cal O}$ that approximates O and for every $x,y\in{\cal L}$ s.t. $x\leq y$ , it holds that ${\cal O}(x,y)\preceq^A_i{\cal O}^{\cal U}(x,y)$ .

In conclusion, non-deterministic AFT admits, just like deterministic AFT, an ultimate approximation. However, as we will see in the rest of this section, the ultimate non-deterministic approximation operator ${\cal O}^{\cal U}$ does not generalize the deterministic ultimate approximation operator defined by Denecker et al. (2002). In more detail, we compare the non-deterministic ultimate operator ${\cal IC}^{\cal U}_{\cal P}$ with the deterministic ultimate ${\cal IC}^{\sf DMT}_{\cal P}$ from Definition 2. Somewhat surprisingly, even when looking at normal logic programs, the operator ${\cal IC}^{\sf DMT^d}_{\cal P}$ does not coincide with the ultimate ndao ${\cal IC}^{\cal U}_{\cal P}$ (and thus ${\cal IC}^{\sf DMT^d}_{\cal P}$ is not the most precise ndao, even for non-disjunctive programs). The intuitive reason is that the additional expressivity of non-deterministic operators, which are not restricted to single lower and upper bounds in their outputs, allows to more precisely capture what is derivable in the “input interval” (x,y).

Example 3 (Example 2 continued)

Consider again ${\cal P}=\{q\leftarrow \lnot p; p\leftarrow p\}$ . Applying the ${\sf DMT^d}$ -operator gives: ${\cal IC}_{\cal P}^{{\sf DMT^d}}(\emptyset,\{p,q\})=(\emptyset,\{p,q\})$ . Intuitively, the ultimate semantics ${\cal IC}_{\cal P}^{\cal U}(\emptyset,\{p,q\})=\{\{p\},\{q\}\}\times \{\{p\},\{q\}\}$ gives us the extra information that we will always either derive p or q, which is information a deterministic approximator can simply not capture. Such a “choice” is not expressible within a single interval; hence, the deterministic ultimate approximation is $(\emptyset,\{p,q\})$ . This example also illustrates the fact that, when applying the ultimate ndao-construction to (non-constant) deterministic operators O, ${\cal O}^{\cal U}$ might be a non-deterministic approximation operator.

However, one can still generalize the operator ${\cal IC}^{\sf DMT^d}_{\cal P}$ to disjunctive logic programs. We first generalize the idea behind ${\cal IC}_{\cal P}^{{\sf DMT^d},l}$ to an operator gathering the heads of rules that are true in every interpretation z in the interval [x,y]. Similarly, ${\cal IC}_{\cal P}^{{\sf DMT^d},u}$ is generalized by gathering the heads of rules with bodies that are true in at least one interpretation in [x,y]:

\[{\cal HD}^{{\sf DMT},l}_{\cal P}(x,y)=\bigcap_{x\subseteq z\subseteq y} \mathit{HD}_{\cal P}(z)\quad \mbox{ and }\quad {\cal HD}^{{\sf DMT},u}_{\cal P}(x,y)=\bigcup_{x\subseteq z\subseteq y} \mathit{HD}_{\cal P}(z)\}.\]

The upper and lower immediate consequences operator are then straightforwardly defined, that is, by taking all interpretations that only contain atoms in ${\cal HD}^{{\sf DMT},\dagger}_{\cal P}(x,y)$ and contain at least one member of every head $\Delta\in {\cal HD}^{{\sf DMT},\dagger}_{\cal P}(x,y)$ (for $\dagger\in \{u,l\}$ ):

\[{\cal IC}_{\cal P}^{{\sf DMT},\dagger}(x,y)=\{z\subseteq \bigcup{\cal HD}^{{\sf DMT},\dagger}_{\cal P}(x,y) \mid \forall \Delta\in{\cal HD}^{{\sf DMT},\dagger}_{\cal P}(x,y)\neq\emptyset: z\cap \Delta\neq \emptyset\}.\]

Finally, the ${\sf DMT}$ -ndao is defined as: ${\cal IC}_{\cal P}^{{\sf DMT}}(x,y)={\cal IC}_{\cal P}^{{\sf DMT},l}(x,y)\times {\cal IC}_{\cal P}^{{\sf DMT},u}(x,y)$ . We have

Proposition 2 (Heyninck et al. 2022, Proposition 3)

For any disjunctive logic program ${\cal P}$ , ${\cal IC}_{\cal P}^{{\sf DMT}}$ is an ndao that approximates $IC_{\cal P}$ .

Notice that for a non-disjunctive program ${\cal P}$ , $\bigcup{\cal IC}_{\cal P}^{{\sf DMT},\dagger}(x,y)= \bigcup{\cal HD}^{{\sf DMT},\dagger}_{\cal P}(x,y)={\cal IC}_{\cal P}^{{\sf DMT^d},\dagger}(x,y)$ (for $\dagger\in \{u,l\}$ ), that is, the non-deterministic version reduces to the deterministic version when looking at non-disjunctive programs. Notice furthermore the operators ${\cal HD}^{{\sf DMT},l}_{\cal P}(x,y)$ and ${\cal HD}^{{\sf DMT},u}_{\cal P}(x,y)$ are only defined for consistent interpretations (x,y). We leave the extension of this operator to inconsistent interpretations for future work.

Example 4 Consider again the program ${\cal P}=\{p\lor q\leftarrow \lnot q\}$ from Example 1. ${\cal IC}^{{\sf DMT},l}_{\cal P}$ behaves as follows:

• • If $q\in y$ then ${\cal HD}^{{\sf DMT},l}_{\cal P}(x,y)=\emptyset$ and thus ${\cal IC}^{{\sf DMT},l}_{\cal P}(x,y)=\emptyset$ .

• • If $q\not\in y$ then ${\cal HD}^{{\sf DMT},l}_{\cal P}(x,y)=\{\{p,q\}\}$ and ${\cal IC}^{{\sf DMT},l}_{\cal P}(x,y)=\{\{p\},\{q\},\{p,q\}\}$ .

${\cal IC}^{{\sf DMT},u}_{\cal P}$ behaves as follows:

• • If $q\in x$ then ${\cal HD}^{{\sf DMT},u}_{\cal P}(x,y)=\emptyset$ and thus ${\cal IC}^{{\sf DMT},u}_{\cal P}(x,y)=\emptyset$ .

• • If $q\not\in x$ then ${\cal HD}^{{\sf DMT},u}_{\cal P}(x,y)=\{\{p,q\}\}$ and thus ${\cal IC}^{{\sf DMT},u}_{\cal P}(x,y)=\{\{p\},\{q\},\{p,q\}\}$ .

Thus, for example, ${\cal IC}^{\sf DMT}_{\cal P}(\emptyset,\{p,q\})= \{\emptyset\}\times \{\{p\},\{q\},\{p,q\}\}$ and ${\cal IC}^{\sf DMT}_{\cal P}(\{p\},\{p\})=\{\{p\},\{q\},\{p,q\}\}\times \{\{p\},\{q\},\{p,q\}\}$ . We thus see that $(\{p\},\{p\})$ is a stable fixpoint of ${\cal IC}^{\sf DMT}_{\cal P}$ .

A slightly extended program ${\cal P}=\{q\leftarrow \lnot q; p\lor q\leftarrow q\}$ shows some particular but unavoidable behavior of this operator. ${\cal IC}^{{\sf DMT},l}_{\cal P}(\emptyset,\{q\})=\{\emptyset\}$ as $\mathit{HD}_{\cal P}(\emptyset)=\{\{q\}\}$ and $\mathit{HD}_{\cal P}(\{q\})=\{\{p,q\}\}$ . Note that the lower bound for is not the stronger $\{p\}$ . This would result in a loss of $\preceq^A_i$ -monotonicity, as the lower bound $\{\{q\}\}$ for the less informative $(\emptyset,\{q\})$ would be $\preceq^S_L$ -incomparable to the lower bound $\{\{p\},\{q\},\{p,q\}\}$ of the more informative $(\{q\},\{q\})$ .

We have shown in this section that non-deterministic AFT admits an ultimate operator, thus providing a way to construct an ndao based on a non-deterministic operator. We have also shown that the ultimate ndao diverges from the ultimate operator for deterministic AFT, but that this deterministic ultimate operator can be generalized to disjunctive logic programs. Both operators will be used in Section 5 to define semantics for dlps with aggregates.

4 Semi-equilibrium semantics

To further extend the reach of non-deterministic AFT, we generalize yet another semantics for dlps, namely the semi-equilibrium semantics (Amendola et al. 2016). The semi-equilibrium semantics is a semantics for disjunctive logic programs that has been studied for disjunctively normal logic programs. This semantics is a three-valued semantics that fulfills the following properties deemed desirable by Amendola et al. (2016): (1) every (total) answer set of ${\cal P}$ corresponds to a semi-equilibrium model; (2) if ${\cal P}$ has a (total) answer set, then all of its semi-equilibrium models are (total) answer sets; (3) if ${\cal P}$ has a classical model, then ${\cal P}$ has a semi-equilibrium model. We notice that these conditions can be seen as a view on approximation of the total stable interpretations alternative to the well-founded semantics. We do not aim to have the last word on which semantics is the most intuitive or desirable. Instead, we will show here that semi-equilibrium models can be represented algebraically and thus can be captured within AFT. This leaves the choice of exact semantics to the user once an ndao has been defined, and allows the use of the semi-equilibrium semantics for formalisms other than nlps, such as disjunctive logic programs with aggregates (see below) or conditional ADFs.

Semi-equilibrium models are based on the logic of here-and-there (Pearce 2006). An HT-interpretation is a pair (x,y) where $x\subseteq y$ (i.e., a consistent pair in AFT-terminology). Satisfaction of a formula $\phi$ , denoted $\models_{\sf HT}$ , is defined recursively as follows:

• • $(x,y)\models_{\sf HT} \alpha$ if $\alpha\in x$ for any $\alpha\in {\cal A}_{\cal P}$ ,

• • $(x,y)\models_{\sf HT} \lnot \phi$ if $(y,y)(\phi)\neq{\sf T}$ , and $(x,y)\not\models_{\sf HT} \bot$ ,

• • $(x,y)\models_{\sf HT} \phi\land[\lor]\psi$ if $(x,y)\models_{\sf HT} \phi$ and [or] $(x,y)\models_{\sf HT} \psi$ ,

• • $(x,y)\models_{\sf HT} \phi\rightarrow \psi$ if (a) $(x,y)\not\models_{\sf HT}\phi$ or $(x,y)\models_{\sf HT}\psi$ , and (b) $(y,y)(\lnot \phi\lor\psi)={\sf T}$ .

The ${\sf HT}$ -models of ${\cal P}$ are defined as ${\sf HT}({\cal P})=\{(x,y)\mid \forall\psi\leftarrow \phi\in {\cal P}: (x,y)\models_{\sf HT}\phi\rightarrow \psi\}$ .

Semi-equilibrium models are a special class of ${\sf HT}$ -models. They are obtained by performing two minimization steps on the set of ${\sf HT}$ -models of a program. The first step is obtained by minimizing w.r.t. $\leq_t$ .¹¹ The second step is obtained by selecting the maximal canonical models. For this, the gap of an interpretation is defined as $gap(x,y)=y\setminus x$ ,¹² and, for any set of interpretations $\mathbf{X}$ , the maximally canonical interpretations are $mc(\mathbf{X})=\{(x,y)\in \mathbf{X}\mid {\not\exists} (w,z)\in \mathbf{X}: gap(x,y)\supset gap(w,z)\}$ . The semi-equilibrium models of ${\cal P}$ are then defined as: $ \mathcal {{SEQ}}({\cal P})= mc\left( \min_{\leq_t}({\sf HT}({\cal P})\right)$ .

Example 5 We illustrate these semantics with the program ${\cal P}=\{p\leftarrow \lnot p, s\lor q\leftarrow \lnot s, s\lor q\leftarrow \lnot q\}$ . Then ${\sf HT}({\cal P})=\{(x,y)\mid \{p\}\subseteq y\subseteq \{p,q,s\}, x\subseteq y, \{q,s\}\cap y\neq \emptyset\}$ . Furthermore, $\min_{\leq_t} ({\sf HT}({\cal P}))=\{(\emptyset,\{p,q,s\}), (\{q\},\{q,p\}), (\{s\},\{s,p\})\}$ . As $gap(\emptyset,\{p,q,s\})=\{p,q,s\}$ and $gap (\{q\},\{q,p\})=gap (\{s\},\{s,p\})=\{p\}$ , $\mathcal{SEQ}=\{ (\{q\},\{q,p\}), (\{s\},\{s,p\})\}$ .

Before we capture the ideas behind this semantics algebraically, we look a bit deeper into the relationship between ${\sf HT}({\cal P})$ -models and the classical notion of three-valued models of a program (see Section 2.1). We first observe that ${\sf HT}$ -models of a program are a proper superset of the three-valued models of a program:

Proposition 3 Let a disjunctively normal logic program ${\cal P}$ and a consistent intepretation (x,y) be given. Then if (x,y) is a model of ${\cal P}$ , it is an ${\sf HT}$ -model of ${\cal P}$ . However, not every ${\sf HT}$ -model is a model of ${\cal P}$ .

We now define the concept of a ${\sf HT}$ -pair algebraically, inspired by Truszczyński (2006):

Definition 3 Given an ndao ${\cal O}$ approximating a non-determinstic operator O, a pair (x,y) is a HT-pair (denoted $(x,y)\in {\sf HT}({\cal O})$ ) if the following three conditions are satisfied: (1) $x\leq y$ , (2) $O(y)\preceq^S_L y$ , and (3) ${\cal O}_l(x,y)\preceq^S_L x$ .

This simple definition faithfully transposes the ideas behind HT-models to an algebraic context. Indeed, applying it to ${\cal IC}_{\cal P}$ gives use exactly the HT-models of ${\cal P}$ :

Proposition 4 Let some normal disjunctive logic program ${\cal P}$ be given. Then, ${\sf HT}({\cal P})={\sf HT}({\cal IC}_{\cal P})$ .

We now show that exact $\leq_t$ -minimal ${\sf HT}$ -models of ${\cal O}$ are stable interpretations of ${\cal O}$ in our algebraic setting. The opposite direction holds as well: total stable fixpoints are $\leq_t$ -minimal ${\sf HT}$ -pairs of ${\cal O}$ . In fact, every total fixpoint of ${\cal O}$ is a ${\sf HT}$ -pair of ${\cal O}$ . We assume that ${\cal O}$ is upward coherent, that is, for every $x,y\in{\cal L}$ , ${\cal O}_l(x,y)\preceq^S_L {\cal O}_u(x,y)$ . In the appendix of the full version of this article (Heyninck and Bogaerts 2023), we provide more details on upward coherent operators. Notice that all ndaos in this paper are upward coherent.

Proposition 5 Given an upward coherent ndao ${\cal O}$ , (1) if $(x,x)\in {\cal O}(x,x)$ then $(x,x)\in {\sf HT}({\cal O})$ ; and (2) $(x,x)\in \min_{\leq_t}({\sf HT}({\cal O}))$ iff $(x,x)\in S({\cal O})(x,x)$ .

The second concept that we have to generalize to an algebraic setting is that of maximal canonical models. Recall that gap(x,y) consists of the atoms which are neither true nor false, that is, it can be used as a measure of the informativeness or precision of a pair. For the algebraic generalization of this idea, it is useful to assume that the lattice under consideration admits a difference for every pair of elements. ¹³ In more detail, $z\in {\cal L}$ is the difference of y w.r.t. x if $z\sqcap x=\bot$ and $x\sqcup y=x\sqcup z$ . If the difference is unique, we denote it by $x\oslash y$ . As an example, note that any Boolean lattice admits a unique difference for every pair of elements. We can then define $\mathsf{mc}(\mathbf{X})={\arg min}_{(x,y)\in \mathbf{X}}\{y\oslash x\}$ . This allows us to algebraically formulate the semi-equilibrium models of an ndao ${\cal O}$ as:

\[{\cal SEQ}({\cal O})=\mathsf{mc}\left(\min_{\leq_t}( {\sf HT}({\cal O}) )\right)\]

The properties mentioned at the start of this section are preserved, and this definition generalizes the semi-equilibrium models for disjunctive logic programs by Amendola et al. (2016):

Proposition 6 Let an upward coherent ndao ${\cal O}$ over a finite lattice be given s.t. every pair of elements admits a unique difference. Then, ${\cal SEQ}({\cal O})\neq\emptyset$ . Furthermore, if there is some $(x,x)\in \mathsf{mc}(\min_{\leq_t}( {\sf HT}({\cal O}) ))$ then ${\cal SEQ}({\cal O})=\{(x,x)\in {\cal L}^2\mid (x,x)\in S({\cal O})(x,x)\}$ .

Corollary 1 Let a disjunctively normal logic program ${\cal P}$ be given. Then, ${\cal SEQ}({\cal IC}_{\cal P})={\cal SEQ}({\cal P})$ .

In this section, we have shown that semi-equilibrium models can be characterized algebraically. This means semi-equilibrium models can now be obtained for other ndaos (e.g., those from Section 5, as illustrated in the appendix of the full version of this paper (Heyninck and Bogaerts 2023)), thusPlease provide respective citation instead of question mark in the sentence “This means semi-equilibrium models…”. greatly enlarging the reach of these semantics.

We end this section by making a short, informal comparison between the semi-equilibrium models and the well-founded state for ndaos (Heyninck et al. 2022). Both constructions have a similar goal: namely, approximate the (potentially non-existent) total stable interpretations. In the case of the semi-equilibrium models, the set of semi-equilibrium models coincides with the total stable interpretations if they exist, whereas the well-founded state approximates any stable interpretation (and thus in particular the total stable interpretations) but might not coincide with them. When it comes to existence, we have shown here that the semi-equilibrium models exist for any ndao, just like the well-founded state. Thus, the well-founded state and semi-equilibrium models seem to formalize two different notions of approximation. Which notion is most suitable is hard to decide in abstracto but will depend on the exact application context.

5 Application to dlps with aggregates

We apply non-deterministic AFT to disjunctive logic programs with aggregates by studying three ndaos: the ultimate, DMT, and the trivial operators. We show the latter two generalize the ultimate semantics (Pelov et al. 2007), respectively, the semantics by Gelfond and Zhang (2019).

5.1 Preliminaries on aggregates

We survey the necessary preliminaries on aggregates and the corresponding programs, restricting ourselves to propositional aggregates and leaving aggregates with variables for future work.

A set term S is a set of pairs of the form $[ \overline{t}: \mathit{Conj}]$ with t a list of constants and $\mathit{Conj}$ a ground conjunction of standard atoms For example, $[1:p; 2:q; -1:r]$ intuitively assigns 1 to p, 2 to q and $-1$ to r. An aggregate function is of the form f(S) where S is a set term, and f is an aggregate function symbol (e.g., $\#{\tt Sum}$ , $\#{\tt Count}$ or $\#{\tt Max}$ ). An aggregate atom is an expression of the form $f(S)\ast w$ where f(S) is an aggregate function, $\ast\in \{<,\leq,\geq,>,=\}$ and w is a numerical constant. We denote by ${\sf At}(f(S)\ast w)$ the atoms occuring in S.

A disjunctively normal aggregate program consists of rules of the form (where $\Delta$ is a set of propositional atoms, and $\alpha_1,\ldots,\alpha_n,\beta_1,\ldots,\beta_m$ are aggregate or propositional atoms):

\[ \bigvee \Delta\leftarrow \alpha_1,\ldots,\alpha_n,\lnot \beta_1,\ldots,\lnot \beta_m\]

An aggregate symbol is evaluated w.r.t. a set of atoms as follows. First, let x(S) denote the multiset $[t_1 \mid \langle t_1,\ldots,t_n:{Conj}\rangle\in S\mbox{ and }{Conj}\mbox{ is true w.r.t. }x]$ . x(f(S)) is then simply the result of the application of f on x(S). If the multiset x(S) is not in the domain of f, $x(f(s))=\curlywedge$ where $\curlywedge$ is a fixed symbol not occuring in ${\cal P}$ . An aggregate atom $f(S)\ast w$ is true w.r.t. x (in symbols, $x(f\ast w)={\sf T}$ ) if: (1) $x(f(S))\neq \curlywedge$ and (2) $x(f(S))\ast w$ holds; otherwise, $f(S)\ast w$ is false (in symbols, $x(f\ast w)={\sf F}$ ). $\lnot f(S)\ast w$ is true if: (1) $x(f(S))\neq \curlywedge$ and (2) $x(f(S))\ast w$ does not hold; otherwise, $\lnot f(S)\ast w$ is false. Evaluating a conjunction of aggregate atoms is done as usual. We can now straightforwardly generalize the immediate consequence operator for disjunctive logic programs to disjunctive aggregate programs by generalizing $\mathit{HD}_{\cal P}$ to take into account aggregate formulas as described above: $\mathit{HD}_{\cal P}(x)=\{ \Delta\mid \bigvee\Delta\leftarrow \phi\in {\cal P}, x(\phi)={\sf T}\}$ . $\mathit{IC}_{\cal P}$ from Definition 1 is then generalized straightforwardly by simply using the generalized $\mathit{HD}_{\cal P}$ . Thus, the only difference with the immediate consequence operator for dlps is that the set of activated heads $\mathit{HD}_{\cal P}$ now takes into account the truth of aggregates as well.

The first semantics we consider is the one formulated by Gelfond and Zhang (2019) (defined there only for logic programs with aggregates occurring positively in the body of a rule):

Definition 4 Let a disjunctively normal aggregate logic program ${\cal P}$ s.t. for every $\bigvee\Delta\leftarrow \bigwedge_{i=1}^n\alpha_i\land \bigwedge_{j=1}^m \lnot \beta_j\in {\cal P}$ , $\beta_j$ is a normal (i.e., non-aggregate) atom. Then the GZ-reduct of ${\cal P}$ w.r.t. x is defined by doing, for every $r=\bigvee\Delta\leftarrow \bigwedge_{i=1}^n\alpha_i\land \bigwedge_{j=1}^m \lnot \beta_j\in {\cal P}$ , the following: (1) if an aggregate atom $\alpha_i$ is false or undefined for some $i=1,\ldots,n$ , delete r; (2) otherwise, replace every aggregate atom $\alpha_i=f(S)\ast w$ by $\bigcup\{Conj\mbox{ occurs in S}\mid x(Conj)={\sf T}\}$ . We denote the GZ-reduct of ${\cal P}$ by ${\cal P}^x_{\sf GZ}$ . Notice that this is a disjunctively normal logic program. A set of atoms $x\subseteq {\cal A}_{\cal P}$ is a GZ-answer set of ${\cal P}$ if (x, x) is an answer set of ${\cal P}^x_{\sf GZ}$ .

Example 6 Consider the program ${\cal P}=\{p\leftarrow \#{\tt Sum}[1: p,q]>0; p\leftarrow \#{\tt Sum}[1: q]>0; q\leftarrow \#{\tt Sum}[1: s]<1\}$ . We check whether $\{p,q\}$ is a ${\sf GZ}$ -answer set as follows:

1. 1. The ${\sf GZ}$ -reduct is ${\cal P}^{\{p,q\}}_{\sf GZ}=\{ p\leftarrow p,q;\quad p\leftarrow q;\quad q\leftarrow \}.$ In more detail, as $\{p,q\}(\#{\tt Sum}[1: p,q]>0)={\sf T}$ , we replace $\#{\tt Sum}[1: p,q]>0$ in the first rule by the atoms in the condition of this aggregate atom verified by $\{p,q\}$ , namely p and q. Similarly for the other rules.

2. 2. As $\{p,q\}$ (or, to be formally more precise, $(\{p,q\},\{p,q\})$ ) is a minimal model of $\frac{{\cal P}^{\{p,q\}}_{\sf GZ}}{(\{p,q\},\{p,q\})}$ , we see $\{p,q\}$ is a GZ-answer set of ${\cal P}$ .

We now move to the semantics by Denecker et al. (2002). They are defined only for non-disjunctive aggregate programs. They are defined on the basis of the ultimate (deterministic) approximator ${\cal IC}^{\sf DMT}_{\cal P}$ (Definition 2). In more detail, an interpretation (x,y) is ${\sf DMT^d}$ -stable if and only if $(x,y)\in S({\cal IC}^{\sf DMT^d}_{\cal P})(x,y)$ , that is, $x\in lfp({\cal IC}^{\sf DMT^d}_{\cal P}(.,y))$ and $y\in lfp({\cal IC}^{\sf DMT^d}_{\cal P}(x,.))$ .

Example 7 Consider the program ${\cal P}=\{p\leftarrow \#{\tt Sum}[1:p]>0;\quad p\leftarrow \#{\tt Sum}[1:p]<1\}$ . $(\{p\},\{p\})$ is an ${\sf DMT^d}$ -stable model of ${\cal P}$ , but the program has no GZ-stable models.

We first explain why $\{p\}$ is not a GZ-stable model. First, we construct ${\cal P}^{\{p\}}_{\sf GZ}=\{ p\leftarrow p\}$ . Since $\{p\}$ is not a stable model of ${\cal P}^{\{p\}}_{\sf GZ}$ , we see that $\{p\}$ is not a GZ-stable model. Likewise, since ${\cal P}^{\emptyset}_{\sf GZ}=\{p\leftarrow \emptyset\}$ , we see that $\emptyset$ is not a stable model of ${\cal P}^{\emptyset}_{\sf GZ}$ and therefore not GZ-stable.

To see $\{p\}$ is a ${\sf DMT^d}$ -stable model, observe that ${\cal IC}_{\cal P}^{{\sf DMT^d},l}(\emptyset,\{p\})={\cal IC}_{\cal P}^{{\sf DMT^d},l}(\{p\},\{p\})=\{p\}$ . Thus, $lfp({\cal IC}_{\cal P}^{{\sf DMT^d},l}(.,\{p\})=\{p\}$ , that is, $(\{p\},\{p\})=S({\cal IC}^{\sf DMT^d}_{\cal P})(\{p\},\{p\})$ .

5.2 Non-deterministic approximation operators for disjunctive aggregate programs

We now proceed to define ndaos for disjunctive aggregate programs. The first ndao we consider generalizes the trivial operator (Pelov et al. 2007), which maps two-valued interpretations to their immediate consequences, whereas three-valued interpretations are mapped to the least precise pair $(\emptyset,{\cal A}_{\cal P})$ (or, in the non-deterministic case, $\{\emptyset\}\times \{{\cal A}_{\cal P}\}$ ). We also study the ndao ${\cal IC}^{\sf DMT}_{\cal P}$ based on the deterministic ultimate approximation, and the ultimate ndao ${\cal IC}_{\cal P}^{\cal U}$ .

Definition 5 Given a disjunctively normal aggregate program ${\cal P}$ and a (consistent) interpretation (x,y), let

The ndaos ${\cal IC}^{\sf DMT}_{\cal P}$ and ${\cal IC}^{\cal U}_{\cal P}$ are defined exactly the same as in Section 3 (recall that $\mathit{IC}_{\cal P}(x)$ was generalized for aggregates in Section 5.1). We illustrate these semantics with an example:

Example 8 Let ${\cal P}=\{r\lor q\leftarrow \#{\tt Sum}[1:s]>0; s\leftarrow \#{\tt Sum}[1:r, 1:q]>0\}$ be given.

We first look at ${\cal IC}_{\cal P}^{\sf GZ}$ . As an example of a fixpoint, consider $(\{r,s\},\{r,s\})$ . Notice first that $\#{\tt Sum}[1:r, 1:q]>0$ and $ \#{\tt Sum}[1:r, 1:q]>0$ are true in $\{r,s\}$ . Thus, $\mathit{HD}_{\cal P}=\{\{r,q\},\{s\}\}$ and ${\cal IC}^{{\sf GZ}}_{\cal P}(\{r,s\},\{r,s\})=\{\{r,s\},\{q,s\},\{r,q,s\}\}\times \{\{r,s\},\{q,s\},\{r,q,s\}\}$ .

We now look at the ${\sf DMT}$ -semantics. For this, we first calculate $\mathit{HD}_{\cal P}$ and $\mathit{IC}_{\cal P}$ for all members of $\wp(\{r,q,s\})$ (with $\Delta_1=\{\{r\},\{q\},\{r,q\}\}$ and $\Delta_2=\{\{s,r\},\{s,q\},\{s,r,q\}\}$ ):

We then see that, for example, ${\cal IC}^{\sf DMT}_{\cal P}(\{r,s\},\{r,s\})=\{\{r,s\},\{q,s\},\{r,q,s\}\}\times \{\{r,s\},\{q,s\},\{r,q,s\}\}$ , whereas ${\cal IC}^{\sf DMT}_{\cal P}(\emptyset,\{r,s\})=\{\emptyset\}\times \{ \{r,s\},\{q,s\},\{r,q,s\}\}$ .

We see that ${\cal IC}^{\cal U}_{\cal P}(\{r,s\},\{r,s\})=\{\{r,s\},\{q,s\},\{r,q,s\}\}\times \{\{r,s\},\{q,s\},\{r,q,s\}\}$ , whereas ${\cal IC}^{\cal U}_{\cal P}(\emptyset,\{r,s\})=\wp(\{r,s,q\})\times \wp(\{r,s,q\})$ .

We now show that these operators are approximation operators with increasing orders of precision: ${\cal IC}^{\sf GZ}_{\cal P}$ is the least precise, ${\cal IC}^{\sf DMT}_{\cal P}$ holds a middle ground, and ${\cal IC}^{\cal U}$ is the most precise:

Proposition 7 Let some $\xi\in \{{\sf DMT},{\sf GZ},{\cal U}\}$ and a disjunctively normal aggregate logic program ${\cal P}$ be given. Then ${\cal IC}_{\cal P}^{\xi}(x,y)$ is an ndao approximating $\mathit{IC}_{\cal P}$ . For any (x,y), ${\cal IC}^{\sf GZ}_{\cal P}(x,y)\preceq^A_i {\cal IC}^{\sf DMT}_{\cal P}(x,y)\preceq^A_i {\cal IC}^{\cal U}_{\cal P}(x,y)$ .

The following properties follow from the general properties shown by Heyninck et al. (2022):

Proposition 8 Let some $\xi\in \{{\sf DMT},{\sf GZ},{\cal U}\}$ and a disjunctively normal aggregate logic program ${\cal P}$ be given. Then: (1) $S({\cal IC}^{\epsilon}_{\cal P})(x,y)$ exists for any $x,y\subseteq {\cal A}_{\cal P}$ , and (2) every stable fixpoint of ${\cal IC}_{\cal P}^{\epsilon}$ is a $\leq_t$ -minimal fixpoint of ${\cal IC}_{\cal P}^{\epsilon}$ .

The ndao ${\cal IC}_{\cal P}^{\sf GZ}$ only admits two-valued stable fixpoints, and these two-valued stable fixpoints generalize the GZ-semantics (Gelfond and Zhang 2019):

Proposition 9 If $(x,y)\in \min_{\leq_t}({\cal IC}^{\sf GZ}_{\cal P}(x,y))$ then $x=y$ . Let a disjunctively normal aggregate aggregate logic program ${\cal P}$ s.t. for every $\bigvee\Delta\leftarrow \bigwedge_{i=1}^n\alpha_i\land \bigwedge_{j=1}^m \lnot \beta_j\in {\cal P}$ , $\beta_i$ is a normal atom be given. $(x,x)\in S({\cal IC}^{\sf GZ}_{\cal P})(x,x)$ iff x is a GZ-answer set of ${\cal P}$ .

We finally show that stable semantics based on ${\cal IC}^{\sf DMT}_{\cal P}$ generalize those for non-disjunctive logic programs with aggregates by Denecker et al. (2002).

Proposition 10 Let a non-disjunctive logic program ${\cal P}$ be given. Then, (x,y) is a stable model according to Denecker et al. (2002) iff $(x,y)\in S({\cal IC}^{\sf DMT}_{\cal P})(x,y)$ .

We have shown how semantics for disjunctive aggregate logic programs can be obtained using the framework of non-deterministic AFT, solving the open question (Alviano et al. 2023) of how operator-based semantics for aggregate programs can be generalized to disjunctive programs. This means AFT can be unleashed upon disjunctive aggregate programs, as demonstrated in this paper, as demonstrated in this section. Other semantics, such as the weakly supported semantics, the well-founded state semantics (Heyninck et al. 2022) and semi-equilibrium semantics (Section 4, as in the appendix of the full version of this article Heyninck and Bogaerts 2023) are obtained without any additional effort and while preserving desirable properties shown algebraically for ndaos. None of these semantics have, to the best of our knowledge, been investigated for dlps with aggregates. Other ndaos, left for future work, can likely be obtained straightforwardly on the basis of deterministic approximation operators for aggregate programs that we did not consider in this paper (e.g., the operator defined by Vanbesien et al. (2021) to characterize the semantics of Marek and Remmel (2004) or the bounded ultimate operator introduced by Pelov and Truszczynski (2004).

6 Conclusion, in view of related work

In this paper, we have made three contributions to the theory of non-deterministic AFT: (1) definition of the ultimate operator, (2) an algebraic generalization of the semi-equilibrium semantics, and (3) an application of non-deterministic AFT to dlps with aggregates in the body. To the best of our knowledge, there are only a few other semantics that allow for disjunctive rules with aggregates. Among the best-studied is the semantics by Faber et al. (2004) (so-called FLP-semantics). As the semantics we propose generalize the operator-based semantics for aggregate programs without disjunction, the differences between the FLP-semantics and the semantics proposed here essentially generalize from the non-disjunctive case (see e.g., Alviano et al. 2023).

Among the avenues for future work are an in-depth analysis of the computational complexity of the semantics proposed here, the generalization of the constructions in Section 5 to other semantics (Vanbesien et al. 2021; Alviano et al. 2023), and defining ndaos for rules with choice constructs in the head (Marek et al. 2008), which can be seen as aggregates in the head.