2.1 Syntax and satisfaction of aggregates

In order to characterize the similarities and differences between the main aggregate semantics proposed for propositional logic programs (Denecker et al. Reference Denecker, Pelov, Bruynooghe and Notes2001; Faber et al. Reference Faber, Pfeifer and Leone2011; Ferraris Reference Ferraris2011; Gelfond and Zhang Reference Gelfond and Zhang2019; Liu et al. Reference Liu, Pontelli, Son and TruszczyŃski2010; Marek and Remmel Reference Marek, Remmel, Lifschitz and NiemelÄ2004; Pelov et al. Reference Pelov, Denecker and Bruynooghe2007), we consider a set $\mathcal{P}$ of propositional atoms. An aggregate expression has the form

(1) \begin{equation}\small{AGG}[{w_1:p_1,\dots,w_n:p_n}]{\odot}{w_0},\end{equation}

where $n\geq 0$ and

• $\small{AGG}\in\{\small{SUM}, \small{TIMES}, \small{AVG}, \small{MIN}, \small{MAX}\}$ is the name of an aggregation function,

• ${w_0},w_1,\dots,w_n$ are integers, where $w_i$ is a weight, for $1 \leq i \leq n$ , and ${w_0}$ is a bound,

• $p_1,\dots,p_n$ are propositional atoms from $\mathcal{P}$ , and

• ${\odot}\in\{<,\leq,\geq,>,=,\neq\}$ is a comparison operator.

For an aggregate expression A as in (1), by ${\small{AT}(A)}=\{p_1,\dots,p_n\}$ we denote the set of propositional atoms occurring in A.

Note that the common count aggregation function is a special case of sum such that each weight is 1. Similarly, even and odd are special cases of times such that each weight is $-1$ , the bound is 1, and ${\odot}$ is $=$ or $\neq$ , respectively. More liberal aggregate concepts also account for rational or real-valued weights, formulas instead of propositional atoms only, as well as a second comparison operator and bound (Calimeri et al. Reference Calimeri, Faber, Gebser, Ianni, Kaminski, Krennwallner, Leone, Maratea, Ricca and Schaub2019; Ferraris Reference Ferraris2011). Concerning knowledge representation, Bartholomew et al. (Reference Bartholomew, Lee and Meng2011), Gebser et al. (Reference Gebser, Harrison, Kaminski, Lifschitz and Schaub2015a), and Harrison and Lifschitz (Reference Harrison and Lifschitz2019) provide first-order generalizations of the aggregate semantics by Faber et al. (Reference Faber, Pfeifer and Leone2011) and Ferraris (Reference Ferraris2011), while Gelfond and Zhang (Reference Gelfond and Zhang2019) as well as Pelov et al. (Reference Pelov, Denecker and Bruynooghe2007) genuinely accommodate first-order aggregates. Specific aggregates in the form of cardinality and weight constraints are elaborated by Ferraris and Lifschitz (Reference Ferraris and Lifschitz2005), Liu and You (Reference Liu and You2013), and Simons et al. (Reference Simons, NiemelÄ and Soininen2002).

A rule has the form

(2) \begin{equation}p_1 \vee \dots \vee p_m \leftarrow A_1 \wedge \dots \wedge A_n,\end{equation}

where $m\geq 0$ , $n\geq 0$ , $p_1,\dots,p_m$ are propositional atoms, and $A_1,\dots,A_n$ are aggregate expressions. For a rule r as in (2), let ${H(r)}=\{p_1,\dots,p_m\}$ and ${B(r)}=\{A_1,\dots,A_n\}$ denote the head and body of r. We say that r is non-disjunctive if $|{H(r)}|\leq 1$ , in which case the consequent of (2) is either of the form $p_1$ or $\bot$ , the latter representing an empty disjunction, that is, a contradiction. The rule r is also called a constraint if ${H(r)}=\emptyset$ , and a fact if ${B(r)}=\emptyset$ , where an empty conjunction in the antecedent of (2) is denoted by $\top$ . While the bodies of rules do not explicitly allow for (negated) propositional atoms p, they can easily be represented by aggregate expressions of the form $\small{SUM}[{1:p}]>0$ or $\small{SUM}[{1:p}]<1$ , so that the syntax at hand includes disjunctive rules (Eiter and Gottlob Reference Eiter and Gottlob1995; Gelfond and Lifschitz Reference Gelfond and Lifschitz1991). A program P is a finite set of rules, and we call P a non-disjunctive program if each $r\in{P}$ is non-disjunctive.

An interpretation $X\subseteq\mathcal{P}$ is represented by the set of its true propositional atoms. It allows us to map each aggregate expression A of the form (1) to a multiset ${\omega(A,X)}=[w_i \mid 1\leq i\leq n,p_i\in X]$ of weights, and then to an expression ${\alpha(A,X)}$ where

• for $\small{AGG}=\small{SUM}$ , ${\alpha(A,X)} = \sum_{w\in{\omega(A,X)}}w$ ,

• for $\small{AGG}=\small{TIMES}$ , ${\alpha(A,X)} = \prod_{w\in{\omega(A,X)}}w$ ,

• for $\small{AGG}=\small{AVG}$ , ${\alpha(A,X)} = \left\{ \begin{array}{@{}l@{}l@{}} \sum_{w\in{\omega(A,X)}}w/|{\omega(A,X)}| & \text{, if}\ |{\omega(A,X)}| > 0, \\ \varepsilon & \text{, if}\ |{\omega(A,X)}| = 0, \end{array} \right.$

• for $\small{AGG}=\small{MIN}$ , ${\alpha(A,X)} = \min\{w \mid w\in{\omega(A,X)}\}$ , and

• for $\small{AGG}=\small{MAX}$ , ${\alpha(A,X)} = \max\{w \mid w\in{\omega(A,X)}\}$ .

Note that the average over a (non-empty) multiset of weights can be a rational number, for example, $(1+2)/|[1,2]|=3/2$ . The $\varepsilon$ outcome of taking the average over the empty multiset stands for undefined, while other aggregation functions map the empty multiset to their neutral elements: $\sum_{w\in[]}w=0$ , $\prod_{w\in[]}w=1$ , $\min\{w \mid w\in[]\}=\infty$ , and $\max\{w \mid w\in[]\}=-\infty$ .

For ${\odot}\in\{<,\leq,\geq,>,=,\neq\}$ , by $X\models ({\alpha(A,X)} {\odot} {w_0})$ we denote that ${\alpha(A,X)} {\odot} {w_0}$ holds, and write $X{\not\models} ({\alpha(A,X)} {\odot} {w_0})$ otherwise. Note that $X\models (\infty \geq {w_0})$ , $X\models (\infty > {w_0})$ , $X\models (\infty \neq {w_0})$ , $X\models (-\infty < {w_0})$ , $X\models (-\infty \leq {w_0})$ , and $X\models (-\infty \neq {w_0})$ apply independently of the (integer) bound ${w_0}$ , while $X{\not\models} (\infty < {w_0})$ , $X{\not\models} (\infty \leq {w_0})$ , $X{\not\models} (\infty = {w_0})$ , $X{\not\models} (-\infty \geq {w_0})$ , $X{\not\models} (-\infty > {w_0})$ , $X{\not\models} (-\infty = {w_0})$ , and $X{\not\models} (\varepsilon {\odot} {w_0})$ , for ${\odot}\in\{<,\leq,\geq,>,=,\neq\}$ , are the cases in which ${\alpha(A,X)} {\odot} {w_0}$ cannot hold.

An aggregate expression A of the form (1) is satisfied by an interpretation X, also written $X\models A$ , if $X\models ({\alpha(A,X)} {\odot} {w_0})$ , and otherwise $X{\not\models} A$ denotes that A is unsatisfied by X. The body of a rule r as in (2) is satisfied by X, written $X\models{B(r)}$ , if $X\models A$ for each $A\in{B(r)}$ , and unsatisfied by X, indicated by $X{\not\models} {B(r)}$ , otherwise. Likewise, the head of r is satisfied by X, $X\models{H(r)}$ , if ${H(r)}\cap X \neq \emptyset$ , and otherwise $X{\not\models}{H(r)}$ expresses that H(r) is unsatisfied by X. The rule r is satisfied by X, that is, $X\models r$ , if $X\models {B(r)}$ implies $X\models {H(r)}$ , while r is unsatisfied by X, $X{\not\models} r$ , otherwise. Note that we have $X{\not\models} {H(r)}$ when r is a constraint, so that $X{\not\models} {B(r)}$ is necessary to satisfy a constraint r by X. For a fact r, $X\models {B(r)}$ is instantaneous, and r is satisfied by X only if $X\models {H(r)}$ . Finally, X is a model of a program P, denoted by $X\models {P}$ , if $X\models r$ for every $r\in{P}$ , and we write $X{\not\models} {P}$ otherwise.

Example 1 Consider the program ${P}_1$ consisting of three rules as follows:

\begin{alignat}{1} \tag{$r_1$} & p \leftarrow \small{SUM}[{1:p,-1:q}] \geq 0 \\ \tag{$r_2$} & p \leftarrow \small{SUM}{[1:q]} > 0 \\ \tag{$r_3$} & q \leftarrow \small{SUM}{[1:p]} > 0\end{alignat}

Intuitively, rule $r_1$ requires p to be true if p is true or q is false, rule $r_2$ requires p true if q is true, and rule $r_3$ requires q true if p is true. The four interpretations over the set $\mathcal{P}=\{p,q\}$ of propositional atoms are $X_1=\emptyset$ , $X_2=\{p\}$ , $X_3=\{q\}$ , and $X_4=\{p,q\}$ . We have that ${\alpha(\small{SUM}{[1:p,-1:q]} \geq 0,X_1)}=0$ , so that $X_1\models {B(r_1)}$ but $X_1{\not\models} {H(r_1)}$ . For $X_2$ and $X_3$ , ${\alpha(\small{SUM}{[1:p]} > 0,X_2)}=1$ and ${\alpha(\small{SUM}{[1:q]} > 0,X_3)}=1$ yield $X_2\models {B(r_3)}$ and $X_3\models {B(r_2)}$ , while $X_2{\not\models} {H(r_3)}$ and $X_3{\not\models} {H(r_2)}$ . That is, neither $X_1$ , $X_2$ , nor $X_3$ is a model of ${P}_1$ . The remaining interpretation $X_4$ is such that $X_4\models {B(r)}$ and $X_4\models {H(r)}$ for every $r\in{P}_1$ , so that $X_4$ is a model of ${P}_1$ .

2.2 Satisfiability of aggregates

With the syntax and satisfaction of aggregate expressions at hand, let us turn to the complexity of deciding whether an aggregate expression A is satisfiable, that is, checking whether there is some interpretation $X\subseteq\mathcal{P}$ such that $X\models A$ . To this end, we first note that determining the smallest and greatest feasible outcome, denoted by ${\small{LB}(A)}$ and ${\small{UB}(A)}$ , of the aggregation function in A of the form (1) can be accomplished as follows (where $\varepsilon$ denotes an undefined outcome):

• for $\small{AGG}=\small{SUM}$ , $\begin{array}[t]{@{}l@{}c@{}l@{}} {\small{LB}(A)} {} = {} \sum_{p\in{\small{AT}(A)},{\alpha(A,\{p\})}<0}{\alpha(A,\{p\})}\text{,} \\ \\[-7pt] {\small{UB}(A)} {} = {} \sum_{p\in{\small{AT}(A)},{\alpha(A,\{p\})}>0}{\alpha(A,\{p\})}\text{,} \end{array}$

• for $\small{AGG}=\small{TIMES}$ , let $\begin{array}[t]{@{}l@{}c@{}l@{}} { \begin{array}[t]{@{}r@{}c@{}l@{}} \pi_\pm & {} = {} & \prod_{p\in{{\small AT}(A)},{\alpha(A,\{p\})}\neq 0}{\alpha(A,\{p\})}\text{,} \\ \\[-7pt] \pi_0 & {} = {} & \prod_{p\in{{\small AT}(A)},{\alpha(A,\{p\})}= 0}{\alpha(A,\{p\})}\text{, and} \\ \\[-7pt] w & {} = {} & \max\{{\alpha(A,\{p\})} \mid p\in{{\small AT}(A)}, {\alpha(A,\{p\})}< 0\} \text{ in} \end{array}} \\ \\[-7pt] {{\small LB}(A)} {} = {} \left\{ \begin{array}{@{}l@{}l@{}} \pi_\pm & \text{, if}\ \pi_\pm < 0, \\ \\[-7pt] \pi_\pm/w & \text{, if}\ \pi_\pm > 0\ \text{and}\ w\neq-\infty, \\ \\[-7pt] \pi_0 & \text{, if}\ w=-\infty, \end{array} \right. \\ \\[-7pt] {{\small UB}(A)} {} = {} \left\{ \begin{array}{@{}l@{}l@{}} \pi_\pm & \text{, if}\ \pi_\pm > 0, \\ \\[-7pt] \pi_\pm/w & \text{, if}\ \pi_\pm < 0, \end{array} \right. \end{array}$

• for $\small{AGG}=\small{AVG}$ , $\begin{array}[t]{@{}l@{}c@{}l@{}} {\small{LB}(A)} & {} = {} & \left\{ \begin{array}{@{}l@{}l@{}} \min\{{\alpha(A,\{p\})} \mid p\in{\small{AT}(A)}\} & \text{, if} {\small{AT}(A)}\neq\emptyset, \\ \\[-7pt] \varepsilon & \text{, if} {\small{AT}(A)}=\emptyset, \end{array} \right. \\ \\[-7pt] {\small{UB}(A)} & {} = {} & \left\{ \begin{array}{@{}l@{}l@{}} \max\{{\alpha(A,\{p\})} \mid p\in{\small{AT}(A)}\} & \text{, if} {\small{AT}(A)}\neq\emptyset, \\ \\[-7pt] \varepsilon & \text{, if} {\small{AT}(A)}=\emptyset, \end{array} \right. \end{array}$

• for $\small{AGG}=\small{MIN}$ , $\begin{array}[t]{@{}l@{}c@{}l@{}} {\small{LB}(A)} & {} = {} & \min\{{\alpha(A,\{p\})} \mid p\in{\small{AT}(A)}\}\text{,} \\ \\[-7pt] {\small{UB}(A)} & {} = {} & \infty\text{,} \end{array}$

• for $\small{AGG}=\small{MAX}$ , $\begin{array}[t]{@{}l@{}c@{}l@{}} {\small{LB}(A)} & {} = {} & -\infty\text{,} \\ \\[-7pt] {\small{UB}(A)} & {} = {} & \max\{{\alpha(A,\{p\})} \mid p\in{\small{AT}(A)}\}\text{.} \end{array}$

For the sum aggregation function, the lower and upper bound are obtained by summing over all atoms associated with a negative or positive weight, respectively. In case of avg, we just pick an atom with the smallest or greatest weight, provided that some atom occurs in A. For min and max, either the upper or the lower bound is trivial, and the respective counterpart is obtained by applying the aggregation function to all weights. The times aggregation function is the most sophisticated, as negative weights may swap the sign of its outcome. If the product $\pi_\pm$ over all atoms with a non-zero weight is negative, $\pi_\pm$ yields the lower bound, while it is otherwise divided by the greatest negative weight w (i.e., smallest absolute value), provided that it exists, to achieve a negative outcome. In the remaining case that no negative outcome is feasible, the lower bound $\pi_0$ is zero when there is some atom with the weight zero, or it defaults to one. Finally, the upper bound is given by $\pi_\pm$ if it is positive, and otherwise we divide $\pi_\pm$ by the greatest negative weight w to obtain the greatest positive outcome.

Given ${\small{LB}(A)}$ and ${\small{UB}(A)}$ for an aggregate expression A of the form (1), ${\small{LB}(A)}={\small{UB}(A)}=\varepsilon$ indicates that A is unsatisfiable regardless of the comparison operator ${\odot}$ , which applies only when A matches $\small{AVG}[]{\odot}{w_0}$ . Otherwise, if the comparison operator ${\odot}$ is $<$ or $\leq$ , we have that A is satisfiable if and only if ${\small{LB}(A)}<{w_0}$ or ${\small{LB}(A)}\leq{w_0}$ holds, respectively. The comparison operators $>$ and $\geq$ are dual, and an aggregate expression A including one of them is satisfiable if and only if either ${\small{UB}(A)}>{w_0}$ or ${\small{UB}(A)}\geq{w_0}$ holds. In case ${\odot}$ is $\neq$ , we have that A is satisfiable if and only if ${\small{LB}(A)}\neq{w_0}$ or ${\small{UB}(A)}\neq{w_0}$ holds. These considerations show that checking the satisfiability of an aggregate expression with a comparison operator other than $=$ is tractable, that is, in the complexity class P. The situation gets more involved when ${\odot}$ is $=$ , where the aggregation functions min and max still allow for tractable decisions: an aggregate expression A with $\small{AGG}$ either min or max and $=$ for ${\odot}$ is satisfiable if and only if ${\alpha(A,\{p\})}={w_0}$ for some $p\in{\small{AT}(A)}$ . Unlike that, for $\small{AGG}=\small{SUM}$ and $\small{AGG}=\small{TIMES}$ , deciding whether there is some (non-empty) subset X of ${\small{AT}(A)}$ such that ${\alpha(A,X)}={w_0}$ amounts to the NP-complete subset sum or subset product problem (Garey and Johnson Reference Garey and Johnson1979). Concerning $\small{AGG}=\small{AVG}$ , subset sum can be reduced to checking whether an aggregate expression A with bound 0 is satisfiable: $\small{SUM}[{w_1:p_1,\dots,w_n:p_n}]={w_0}$ with positive integers $w_0,\dots,w_n$ is satisfiable if and only if $\small{AVG}[{w_1:p_1,\dots,w_n:p_n,-{w_0}:p}]=0$ is satisfiable, where $p\in\mathcal{P}$ is some new atom. As constants like ${w_0}+1$ can be added to each weight and the bound of an aggregate expression with avg, we have NP-completeness of checking whether A with $\small{AGG}\in\{\small{SUM},\small{TIMES},\small{AVG}\}$ and $=$ for ${\odot}$ is satisfiable, which applies regardless of whether the included weights and bound are restricted to be positive or negative integers only.

Example 2 Consider aggregate expressions constructed as follows:

\begin{alignat}{1} \tag{$A_1$} \small{SUM}{[1:p_1,3:p_2,3:p_3,-4:p_4]} {\odot} {w_0} \\ \tag{$A_2$} \small{TIMES}{[0:p_1,3:p_2,-2:p_3,-4:p_4]} {\odot} {w_0} \\ \tag{$A_3$} \small{AVG}{[1:p_1,2:p_2,3:p_3,6:p_4]} {\odot} {w_0} \\ \tag{$A_4$} \small{MIN}{[0:p_1,3:p_2,-2:p_3,-4:p_4]} {\odot} {w_0} \\ \tag{$A_5$} \small{MAX}{[1:p_1,3:p_2,3:p_3,-4:p_4]} {\odot} {w_0}.\end{alignat}

By summing up negative or positive weights, respectively, we get ${\small{LB}(A_1)}=-4$ and ${\small{UB}(A_1)}=7$ . Hence, $A_1$ is satisfiable for ${{\odot}}={<}$ and any bound ${w_0}$ greater than $-4$ , for ${{\odot}}={\leq}$ and ${w_0}$ not smaller than $-4$ , for ${{\odot}}={\geq}$ and ${w_0}$ not greater than 7, for ${{\odot}}={>}$ and ${w_0}$ smaller than 7, and for ${{\odot}}={\neq}$ with any bound ${w_0}$ . When ${\odot}$ is $=$ , satisfiability is more intricate, and one can check that $A_1$ is satisfiable for bounds ${w_0}$ other than $-2$ and 5 in the range from ${\small{LB}(A_1)}=-4$ to ${\small{UB}(A_1)}=7$ .

The product of non-zero weights, two of which are negative, for $A_2$ is 24. To obtain the lower bound for $A_2$ , we have thus to divide by the greatest negative weight $-2$ , leading to ${\small{LB}(A_2)}=-12$ , while ${\small{UB}(A_2)}=24$ . For ${\odot}\in\{<,\leq,\geq,>,\neq\}$ , satisfiability is determined similar to $A_1$ , yet w.r.t. the lower and upper bound for $A_2$ . When ${\odot}$ is $=$ , we have that $A_2$ is satisfiable for ${w_0}\in\{-12, -6, -4, -2, 0, 1, 3, 8, 24\}$ , and unsatisfiable otherwise.

Concerning $A_3$ , we get ${\small{LB}(A_3)}=1$ and ${\small{UB}(A_3)}=6$ , and satisfiability for ${\odot}\in\{<,\leq,\geq,>,\neq\}$ w.r.t. these bounds is analogous. As 1, 2, 3, 4, and 6 are the feasible integer outcomes, $A_3$ with $=$ for ${\odot}$ is satisfiable for such outcomes as ${w_0}$ , and unsatisfiable for any other bound ${w_0}$ .

Turning to $A_4$ and $A_5$ , the lower and upper bounds are ${\small{LB}(A_4)}=-4$ , ${\small{UB}(A_4)}=\infty$ , ${\small{LB}(A_5)}=-\infty$ , and ${\small{UB}(A_5)}=3$ . For ${\odot}\in\{<,\leq,\geq,>,\neq\}$ , satisfiability is determined similar to $A_1$ , where $A_4$ is satisfiable for ${{\odot}}={\geq}$ , ${{\odot}}={>}$ , and ${{\odot}}={\neq}$ regardless of the bound ${w_0}$ , and likewise $A_5$ for ${{\odot}}={<}$ , ${{\odot}}={\leq}$ , and ${{\odot}}={\neq}$ . When ${\odot}$ is ${=}$ , we have that $A_4$ and $A_5$ are satisfiable for bounds ${w_0}$ matching their contained weights, that is, ${w_0}\in\{-4,-2,0,3\}$ or ${w_0}\in\{-4,1,3\}$ , respectively.

2.3 Monotonicity of aggregates

A relevant property related to satisfiability concerns the (non)monotonicity of aggregate expressions (cf. Faber et al. (Reference Faber, Pfeifer and Leone2011); Reference Liu, Pontelli, Son and TruszczyŃskiLiu et al. (2010)) and the notion of convex aggregates introduced by Liu and TruszczyŃski (Reference Liu and TruszczyŃski2006). An aggregate expression A is convex if $X \subseteq Y$ , $X \models A$ and $Y \models A$ imply $Z \models A$ for any interpretation Z between X and Y, that is, $X\models A$ and $Y\models A$ yield $Z\models A$ for all $X\subseteq Z\subseteq Y$ . Otherwise, the aggregate expression is non-convex. Two frequent special cases of convexity are given by monotone and anti-monotone aggregate expressions, for which $X\models A$ implies that $\mathcal{P}\models A$ or $\emptyset\models A$ , respectively. That is, a monotone aggregate expression A remains satisfied when adding (true) propositional atoms to an interpretation X satisfying A, while the satisfaction of an anti-monotone A is preserved when propositional atoms from X are falsified.

Specific monotonicity properties that follow from the aggregation functions and comparison operators of aggregate expressions are summarized in Figure 3 in the introduction. For the sum and times aggregation functions, restrictions to positive or negative weights and bounds affect monotonicity, and the subscripts $_+$ and $_-$ indicate such particular conditions. Unlike that, the signs of weights and bounds are immaterial for avg, min, and max, and we also disregard special cases like the unsatisfiability of $\small{AVG}{[]}{\odot}{w_0}$ , which makes aggregate expressions with avg over the empty multiset monotone, anti-monotone, and convex.

While aggregate expressions with sum are in general non-convex regardless of the comparison operator, restrictions to positive or negative weights and bounds make them convex for comparison operators other than $\neq$ , given that the sum of weights can merely increase or decrease when propositional atoms are added to an interpretation. More specifically, positive weights and bounds lead to an anti-monotone aggregate expression for $<$ or $\leq$ as comparison operator, and to a monotone aggregate expression for $\geq$ or $>$ , where dual properties apply in case of negative weights and bounds only. For either restriction, the comparison operator $\neq$ does not lead to more regular monotonicity though because a respective aggregate expression may be satisfied by the empty interpretation $\emptyset$ , become unsatisfied when atoms whose weights sum up to the bound ${w_0}$ are made true, and then get satisfied again by adding further propositional atoms to the interpretation.

Aggregate expressions with times are generally non-convex, even if weights and bounds are restricted to be negative only. This is due to the condition that negative weights swap the sign of the outcome, so that satisfaction may switch back and forth for any comparison operator. With positive weights and bounds (excluding zero), the outcome increases when more propositional atoms are included in an interpretation. Hence, such aggregate expressions yield similar monotonicity as sum with positive weights and bounds, and entries for $\small{SUM}_+$ and $\small{TIMES}_+$ in Figure 3 match.

For the remaining aggregation functions, avg, min, and max, the signs of weights do not make a difference regarding monotonicity. In fact, the outcome of avg may increase or decrease when propositional atoms are added to an interpretation, so that corresponding aggregate expressions are generally non-convex regardless of the comparison operator. The outcomes of min and max monotonically decrease or increase, respectively, with growing interpretations, leading to (anti-)monotonicity for the comparison operators $<$ or $\leq$ and $\geq$ or $>$ , as well as convexity for $=$ . Similar to the other aggregation functions, no matter whether weights and bounds are positive, negative, or unrestricted, $\neq$ as comparison operator makes aggregate expressions with min and max non-convex in general, as they are satisfied by the empty interpretation $\emptyset$ , may become unsatisfied and then satisfied again when the interpretation is extended by propositional atoms.

Example 3 The aggregate expression

\begin{alignat}{1} \tag{$A_6$} \small{SUM}{[1:p_1,2:p_2,2:p_3,3:p_4]} {\odot} 5\end{alignat}

is monotone for ${{\odot}}={\geq}$ or ${{\odot}}={>}$ , anti-monotone for ${{\odot}}={<}$ or ${{\odot}}={\leq}$ , convex when ${\odot}$ is $=$ , and non-convex with $\neq$ for ${\odot}$ . The three mutually incomparable interpretations $\{p_1,p_2,p_3\}$ , $\{p_2,p_4\}$ , and $\{p_3,p_4\}$ satisfying $A_6$ with $=$ for ${\odot}$ meet the condition for convexity, but neither the additional requirements for monotonicity nor anti-monotonicity. Moreover, they witness the non-convexity of $A_6$ when ${\odot}$ is $\neq$ , as there are interpretations with both fewer and more propositional atoms such that their (positive) weights do not sum up to the bound 5 and satisfy $A_6$ for ${{\odot}}={\neq}$ .

3.1 Model-based semantics

In line with Gelfond and Lifschitz (Reference Gelfond, Lifschitz, Kowalski and Bowen1988), Gelfond and Lifschitz (Reference Gelfond and Lifschitz1991), we let the reduct of a program P relative to an interpretation $X\subseteq\mathcal{P}$ be ${{P}^{X}}=\{r\in{P} \mid X\models{B(r)}\}$ . In other words, the reduct is obtained from P by dropping rules whose bodies are unsatisfied by X. (Note that the original definition of reduct provided by Gelfond and Lifschitz (Reference Gelfond, Lifschitz, Kowalski and Bowen1988) also removes negative literals, which are not part of the language considered in this paper.) Hence, we have that X is a model of P if and only if X is a model of ${{P}^{X}}$ .

Different answer set semantics inspect the reduct in specific ways to check the provability of true atoms. We note that our reduct notion matches the definitions given by Faber et al. (Reference Faber, Pfeifer and Leone2011) and Ferraris (Reference Ferraris2011), as it does not eliminate false atoms or falsified expressions, respectively. The latter would happen for negated atoms with the seminal Gelfond–Lifschitz reduct (Gelfond and Lifschitz Reference Gelfond, Lifschitz, Kowalski and Bowen1988; Gelfond and Lifschitz Reference Gelfond and Lifschitz1991), and entirely with the reduct by Ferraris (Reference Ferraris2011). However, the syntax of aggregate expressions and rules in (1)–(2) is chosen such that specific reducts do not make a difference regarding answer sets.

The model-theoretic approaches by Faber et al. Reference Faber, Pfeifer and Leone2011 and Ferraris (Reference Ferraris2011) agree in focusing on $\subseteq$ -minimal models of the reduct ${{P}^{X}}$ of a program P relative to an interpretation $X\subseteq\mathcal{P}$ . We use the convention to indicate particular semantics by their proposers, and call X an FFLP-answer set of P if X is a $\subseteq$ -minimal model of ${{P}^{X}}$ . That is, an FFLP-answer set of P fulfills two conditions:

• X is a model of P, that is, $X\models {P}$ , and

• for any interpretation $Y\subset X$ , we have that $Y{\not\models}{{P}^{X}}$ .

While the first condition is equivalent to $X\models {{P}^{X}}$ , exchanging $Y{\not\models}{{P}^{X}}$ for $Y{\not\models} {P}$ in the second condition would yield a different semantics.

Example 4 Consider the program ${P}_2$ containing the following two rules:

\begin{alignat}{1} \tag{$r_4$} & p \leftarrow \small{SUM}{[1:p]} > 0 \\ \tag{$r_5$} & p \leftarrow \small{SUM}{[1:p]} < 1\end{alignat}

Intuitively, rule $r_4$ requires p true if p is true, and rule $r_5$ requires p true if p is false. The interpretation $X_1=\emptyset$ is not a model of ${P}_2$ because ${\alpha(\small{SUM}{[1:p]} < 1,X_1)}=0$ yields that $X_1\models {B(r_5)}$ but $X_1{\not\models} {H(r_5)}$ . For $X_2=\{p\}$ , we have that ${\alpha(\small{SUM}{[1:p]} < 1,X_2)}=1$ , so that $X_2{\not\models} {B(r_5)}$ . Hence, ${{P}_2^{X_2}}$ consists of the rule r ₄ only. Since $X_1\subset X_2$ is such that ${\alpha(\small{SUM}{[1:p]} > 0,X_1)}=0$ , $X_1{\not\models} {B(r_4)}$ , and $X_1\models {{P}_2^{X_2}}$ , the interpretation $X_1$ shows that $X_2$ is not a $\subseteq$ -minimal model of ${{P}_2^{X_2}}$ . As a consequence, the program ${P}_2$ does not have any FFLP-answer set. However, note that $X_2$ is the $\subseteq$ -minimal model of ${P}_2$ in view of $X_2\models {P}_2$ and $X_1{\not\models} {P}_2$ .

Example 5 Reconsider the program ${P}_1$ from Example 1:

\begin{alignat}{1} \tag{$r_1$} & p \leftarrow \small{SUM}{[1:p,-1:q]} \geq 0 \\ \tag{$r_2$} & p \leftarrow \small{SUM}{[1:q]} > 0 \\ \tag{$r_3$} & q \leftarrow \small{SUM}{[1:p]} > 0\end{alignat}

As checked in Example 1, we have that $X_4=\{p,q\}$ is the unique model of ${P}_1$ (over the set $\mathcal{P}=\{p,q\}$ of propositional atoms). Given that $X_4\models {B(r)}$ for every $r\in{P}_1$ , we obtain ${{P}_1^{X_4}}={P}_1$ , which shows that $X_4$ is an FFLP-answer set of ${P}_1$ .

Example 6 Consider the program ${P}_3$ consisting of the following rules:

\begin{alignat}{1} \tag{$r_6$} & x_1 \leftarrow \small{SUM}{[1:y_1]} < 1 \\ \tag{$r_7$} & y_1 \leftarrow \small{SUM}{[1:x_1]} < 1 \\ \tag{$r_8$} & x_2 \leftarrow \small{SUM}{[1:y_2]} < 1 \\ \tag{$r_9$} & y_2 \leftarrow \small{SUM}{[1:x_2]} < 1 \\ \tag{$r_{10}$} & z_1 \leftarrow \small{SUM}{[1:p]} > 0 \\ \tag{$r_{11}$} & z_2 \leftarrow \small{SUM}{[1:p]} > 0 \\ \tag{$r_{12}$} & p \leftarrow \small{SUM}{[1:y_1,2:y_2,2:z_1,3:z_2]} \neq 5 \\ \tag{$r_{13}$} & \bot \leftarrow \small{SUM}{[1:p]} < 1\end{alignat}

As will be clarified later in Section 4 and Example 14, ${P}_3$ (under FFLP-, LPST-, or DPB-answer set semantics) encodes an instance of generalized subset sum (Berman et al. Reference Berman, Karpinski, Larmore, Plandowski and Rytter2002), specifically

\begin{alignat*}{1}\exists y_1 y_2 \forall z_1 z_2 (1 \cdot y_1 + 2 \cdot y_2 + 2 \cdot z_1 + 3 \cdot z_2 \neq 5)\text{.}\end{alignat*}

Intuitively, rules $r_6$ and $r_7$ are intended to select exactly one of $x_1$ and $y_1$ , and similarly rules $r_8$ and $r_9$ are intended to select exactly one of $x_2$ and $y_2$ ; these rules represent the existential variables of the generalized subset sum instance. Rules $r_{10}$ and $r_{11}$ require $z_1$ and $z_2$ to be true if p is true; these rules represent the universal variables of the generalized subset sum instance. Rule $r_{13}$ enforces p true, but does not provide a justification for it, which instead must be provided by rule $r_{12}$ , encoding the inequality of the generalized subset sum instance. Note that ${P}_3$ follows the saturation technique by Eiter and Gottlob (Reference Eiter and Gottlob1995) to express that $z_1$ and $z_2$ are universally quantified: $z_1$ and $z_2$ must be true because of p (they are saturated), while p (and $z_1$ , $z_2$ ) are provable if and only if the universal quantification holds w.r.t. the chosen (true) subset of $\{y_1,y_2\}$ .

Let us focus on interpretations that are potential candidates for FFLP-answer sets of ${P}_3$ . In view of the constraint $r_{13}$ , each model of ${P}_3$ must include the atom p, and then the atoms $z_1$ and $z_2$ because of the rules $r_{10}$ and $r_{11}$ . Regarding $x_i$ and $y_i$ for $1\leq i\leq 2$ , having both atoms false yields unsatisfied rules $r_6$ and $r_7$ or $r_8$ and $r_9$ , while both atoms true lead to a reduct excluding $r_6$ and $r_7$ or $r_8$ and $r_9$ . In the latter case, falsifying $x_i$ and $y_i$ gives a smaller model of the reduct, so that the original interpretation cannot be an FFLP-answer set of ${P}_3$ .

The previous considerations leave the models $X_1=\{x_1,x_2,z_1,z_2,p\}$ , $X_2=\{x_1,y_2,z_1,z_2,p\}$ , $X_3=\{y_1,x_2,z_1,z_2,p\}$ , and $X_4=\{y_1,y_2,z_1,z_2,p\}$ as potential FFLP-answer sets of ${P}_3$ . For each of these interpretations, the reduct includes either of the rules $r_6$ or $r_7$ as well as $r_8$ or $r_9$ , so that falsifying an atom $x_i$ or $y_i$ leads to unsatisfaction of the rule with the atom in the head. A smaller model of the reduct must thus falsify p along with an appropriate combination of the atoms $z_1$ and $z_2$ , in order to establish the unsatisfaction of ${B(r_{12})}$ . Note that the reduct does not include the constraint $r_{13}$ , which enables the falsification of p, provided that ${B(r_{12})}$ is unsatisfied.

For $X_1$ , the observation that ${\alpha(\small{SUM}{[1:y_1, 2:y_2, 2:z_1, 3:z_2]} \neq 5,X_1)}=5$ yields $X_1{\not\models} {B(r_{12})}$ and $r_{12}\notin{{P}_3^{X_1}}$ , so that $Y_1\models {{P}_3^{X_1}}$ , for each $\{x_1,x_2\}\subseteq Y_1\subseteq X_1\setminus\{p\}$ , disproves $X_1$ to be an FFLP-answer set of ${P}_3$ . Regarding $X_2$ and $X_4$ , we have that $Y_2=X_2\setminus\{z_1,p\}=\{x_1,y_2,z_2\}$ and $Y_4=X_4\setminus\{z_2,p\}=\{y_1,y_2,z_1\}$ furnish counterexamples satisfying the respective reduct in view of $Y_2{\not\models} {B(r_{12})}$ and $Y_4{\not\models} {B(r_{12})}$ . It thus remains to investigate $X_3$ , where ${{P}_3^{X_3}}=\{{r_7},{r_8},{r_{10}},r_{11},r_{12}\}$ and ${\alpha(\small{SUM}{[1:y_1, 2:y_2, 2:z_1, 3:z_2]} \neq 5,X_3)}=6$ . That is, an interpretation $Y_3\subset X_3$ with ${\alpha(\small{SUM}{[1: y_1, 2:y_2, 2:z_1, 3:z_2]} \neq 5,Y_3)}=5$ can only be obtained by falsifying $y_1$ , which leads to $Y_3{\not\models} r_7$ . In turn, $Y\models {B(r_{12})}$ is the case for every model $Y\subseteq X_3$ of ${{P}_3^{X_3}}$ , leaving $Y=X_3$ as the unique such interpretation. Hence, we conclude that $X_3$ is a $\subseteq$ -minimal model of ${{P}_3^{X_3}}$ and thus an FFLP-answer set of ${P}_3$ .

3.2 Construction-based semantics

While the aggregate semantics by Faber et al. (Reference Faber, Pfeifer and Leone2011) and Ferraris (Reference Ferraris2011) build on $\subseteq$ -minimal models of a reduct, without considering the calculation of such models in the first place, the semantics given by Gelfond and Zhang (Reference Gelfond and Zhang2019), Liu et al. Reference Liu, Pontelli, Son and TruszczyŃski2010, Marek and Remmel (Reference Marek, Remmel, Lifschitz and NiemelÄ2004), and Denecker et al. Reference Denecker, Pelov, Bruynooghe and Notes2001 focus on constructive characterizations for checking the provability of true atoms. In particular, the semantics by Gelfond and Zhang (Reference Gelfond and Zhang2019) and Liu et al. (Reference Liu, Pontelli, Son and TruszczyŃski2010), referred to as GZ- and LPST-answer set semantics indicated by their proposers, are based on a monotone fixpoint construction to check the stability of an answer set candidate X, which amounts to testing whether all atoms of X (and only those) can be constructed/derived from the rules, assuming that atoms not contained in X are fixed to false. The family of semantics by Pelov et al. (Reference Pelov, Denecker and Bruynooghe2007), defined in terms of approximation fixpoint theory, provides a strongly related approach: for each suitable choice of a three-valued truth assignment function mapping each aggregate expression to true, false, or unknown w.r.t. a partial interpretation, the framework induces an answer set, a well-founded, and a Kripke–Kleene semantics. As shown by Vanbesien et al. (Reference Vanbesien, Bruynooghe and Denecker2021), the particular truth assignment functions for trivial and ultimate approximating aggregates (Pelov et al. Reference Pelov, Denecker and Bruynooghe2007) lead exactly to the GZ- or LPST-answer set semantics, respectively. In addition, Pelov et al. (Reference Pelov, Denecker and Bruynooghe2007) proposed a truth assignment function for bound approximating aggregates, based on evaluating lower and upper bounds like ${\small{LB}(A)}$ and ${\small{UB}(A)}$ in Section 2.2, which achieves provability for more answer set candidates than the GZ-answer set semantics without increasing the computational complexity. Given such close relationships, we do not separately address trivial, ultimate, and bound approximating aggregates, but focus on the so-called ultimate semantics, originally introduced in earlier work (Denecker et al. Reference Denecker, Pelov, Bruynooghe and Notes2001), as a complementary instance of the framework by Pelov et al. (Reference Pelov, Denecker and Bruynooghe2007).

In the following, we describe the constructions characterizing the aforementioned semantics by dedicated extensions of the well-known immediate consequence operator ${{\mathcal{T}}_{{P}}}$ (van Emden and Kowalski Reference van Emden and Kowalski1976; Lloyd Reference Lloyd1987) to programs with aggregate expressions. We start by specifying particular notions of satisfaction, again indicated by the proposers of a semantics, of an aggregate expression A relative to two interpretations $Y\subseteq \mathcal{P},X\subseteq \mathcal{P}$ , where X is an answer set candidate and Y is the reconstructed model:

• $(Y,X) {\models_{\small{GZ}}} A$ if $X\models A$ and ${\small{AT}(A)}\cap Y = {\small{AT}(A)}\cap X$ ,

• $(Y,X) {\models_{\small{LPST}}} A$ if $Z\models A$ for every interpretation $Y\subseteq Z\subseteq X$ , and

• $(Y,X) {\models_{\small{MR}}} A$ if $X\models A$ and there is some interpretation $Z\subseteq Y$ such that $Z\models A$ .

When $Y\subseteq X$ , the satisfaction relations ${\models_{\small{GZ}}}$ , ${\models_{\small{LPST}}}$ , and ${\models_{\small{MR}}}$ can apply only if $X\models A$ , which parallels the idea of a reduct relative to X. Their second purpose is to determine partial interpretations (Y,X), where the truth of atoms in $X\setminus Y$ is considered unknown, for which an aggregate expression A should be regarded as provably true: $(Y,X) {\models_{\small{GZ}}} A$ expresses that no unknown atoms from $X\setminus Y$ occur in A, $(Y,X) {\models_{\small{LPST}}} A$ means that A is satisfied no matter which unknown atoms are taken to be true or false, respectively, and $(Y,X) {\models_{\small{MR}}} A$ merely requires the satisfaction of A by some subset of the true atoms in Y. Unlike that, the ultimate semantics relies on the conventional satisfaction of aggregate expressions, as introduced in Section 2.2. Similar to $X\models {B(r)}$ , we extend ${\models_{{\Delta}}}$ , for ${\Delta}\in\{\small{GZ},\small{LPST},\small{MR}\}$ , to the body of a rule r by writing $(Y,X) {\models_{{\Delta}}} {B(r)}$ if $(Y,X) {\models_{{\Delta}}} A$ for each $A\in{B(r)}$ , and indicate that $(Y,X) {{\not\models}_{{\Delta}}} A$ , for some $A\in{B(r)}$ , by $(Y,X) {{\not\models}_{{\Delta}}} {B(r)}$ .

Example 7 Let us investigate the aggregate expression

\begin{alignat}{1} \tag{$A_7$} \small{SUM}{[1:y_1,2:y_2,2:z_1,3:z_2]} \neq 5\end{alignat}

along with the interpretation $X=\{y_1,z_1,z_2\}$ , where ${\alpha(A_7,X)}=6$ and thus $X\models A_7$ . The condition for $(Y,X) {\models_{\small{GZ}}} A_7$ additionally requires ${\small{AT}(A_7)}\cap Y={\small{AT}(A_7)}\cap X=\{y_1,z_1,z_2\}$ , so that $Y=X=\{y_1,z_1,z_2\}$ is the only subset of X for which ${\models_{\small{GZ}}}$ applies. For identifying interpretations $Y\subseteq X$ such that $(Y,X) {\models_{\small{LPST}}} A_7$ , observe that ${\alpha(A_7,\{z_1,z_2\})}=5$ and $\{z_1,z_2\}{\not\models} A_7$ . That is, any subset of X that excludes $y_1$ can be filled up to the interpretation $Z=\{z_1,z_2\}$ for which $A_7$ is unsatisfied. In turn, such a Z does not exist for interpretations $\{y_1\}\subseteq Y\subseteq X$ , and we have $(Y,X) {\models_{\small{LPST}}} A_7$ for each subset Y of X that includes $y_1$ . Regarding $(Y,X) {\models_{\small{MR}}} A_7$ , it is sufficient to observe that ${\alpha(A_7,\emptyset)}=0$ and $\emptyset\models A_7$ , so that ${\models_{\small{MR}}}$ applies for every subset Y of X.

Provided that $Y\subseteq X\subseteq \mathcal{P}$ , we have that $(Y,X) {\models_{\small{GZ}}} A$ implies $(Y,X) {\models_{\small{LPST}}} A$ , and also that $(Y,X) {\models_{\small{LPST}}} A$ implies $(Y,X) {\models_{\small{MR}}} A$ . Moreover, $(Y,X) {\models_{{\Delta}}} A$ yields $(Z,X) {\models_{{\Delta}}} A$ for interpretations $Y\subseteq Z\subseteq X$ and ${\Delta}\in\{\small{GZ},\small{LPST},\small{MR}\}$ . These properties carry forward to the body B(r) of a rule r.

Given the specific satisfaction relations, we now formulate immediate consequence operators characterizing semantics based on constructions for a program P and interpretations $Y\subseteq \mathcal{P}, X\subseteq \mathcal{P}$ :

\begin{alignat*}{1}{{{{\mathcal{T}}_{{P},X}}^{{\Delta}}}(Y)} & {} = \text{$\bigcup$}_{r\in{P},(Y,X){\models_{{\Delta}}}{B(r)}}{H(r)}\text{, for ${\Delta}\in\{\small{GZ},\small{LPST},\small{MR}\}$,}\\[4pt]{{{{\mathcal{T}}_{{P},X}}^{\small{DPB}}}(Y)} & {} = \text{$\bigcap$}_{Y\subseteq Z\subseteq X} \left( \text{$\bigcup$}_{r\in{P},Z\models{B(r)}}{H(r)} \right)\text{.}\end{alignat*}

Each operator ${{{\mathcal{T}}_{{P},X}}^{{\Delta}}}$ , for ${\Delta}\in\{\small{GZ},\small{LPST},\small{MR},\small{DPB}\}$ , joins the heads of rules such that the underlying satisfaction relation applies to their bodies. This would yield unintended results for (proper) disjunctive rules like $p\vee q\leftarrow \top$ , having $\{p\}$ and $\{q\}$ as its standard answer sets (Gelfond and Lifschitz Reference Gelfond and Lifschitz1991), while any of the operators ${{{\mathcal{T}}_{{P},X}}^{{\Delta}}}$ would produce the non-minimal model $\{p,q\}$ . In fact, such immediate consequence operators have been devised with non-disjunctive rules in mind, and in the following we assume that $|{H(r)}|\leq 1$ for rules r under consideration. For the sake of completeness, we point out that the semantics by Gelfond and Zhang (Reference Gelfond and Zhang2019), Liu et al. (Reference Liu, Pontelli, Son and TruszczyŃski2010), and Marek and Remmel (Reference Marek, Remmel, Lifschitz and NiemelÄ2004) additionally allow for aggregate expressions in heads of rules, understood as choice constructs (Simons et al. Reference Simons, NiemelÄ and Soininen2002), and Gelfond and Zhang (Reference Gelfond and Zhang2019) also handle disjunctive rules, as their original concept builds on a specific reduct rather than an operational characterization.

The operators ${{{\mathcal{T}}_{{P},X}}^{{\Delta}}}$ have in common that ${{{{\mathcal{T}}_{{P},X}}^{{\Delta}}}(Y)} \subseteq {{{{\mathcal{T}}_{{P},X}}^{{\Delta}}}(Z)}$ when $Y\subseteq Z\subseteq X$ . Considering ${{{\mathcal{T}}_{{P},X}}^{\small{DPB}}}$ , this is because the intersection over interpretations between Z and X involves fewer elements than with Y, while $(Y,X){\models_{{\Delta}}}{B(r)}$ implies $(Z,X){\models_{{\Delta}}}{B(r)}$ for the remaining operators ${{{\mathcal{T}}_{{P},X}}^{{\Delta}}}$ and any rule $r\in{P}$ . Provided that X is a model of P, in which case ${{{{\mathcal{T}}_{{P},X}}^{\small{GZ}}}(X)} = {{{{\mathcal{T}}_{{P},X}}^{\small{LPST}}}(X)} = {{{{\mathcal{T}}_{{P},X}}^{\small{MR}}}(X)} = {{{{\mathcal{T}}_{{P},X}}^{\small{DPB}}}(X)} \subseteq X$ , the least fixpoint of ${{{\mathcal{T}}_{{P},X}}^{{\Delta}}}$ is thus guaranteed to exist and can be constructed as follows:

\begin{alignat*}{1}{{{{\mathcal{T}}_{{P},X}}^{{\Delta}}}\uparrow 0} & {} = \emptyset\text{,}\\[3pt]{{{{\mathcal{T}}_{{P},X}}^{{\Delta}}}\uparrow i+1} & {} = {{{{\mathcal{T}}_{{P},X}}^{{\Delta}}}({{{{\mathcal{T}}_{{P},X}}^{{\Delta}}}\uparrow i})}\text{.}\end{alignat*}

That is, starting from the empty interpretation $\emptyset$ for ${{{{\mathcal{T}}_{{P},X}}^{{\Delta}}}\uparrow 0}$ , the iterated application of ${{{\mathcal{T}}_{{P},X}}^{{\Delta}}}$ leads to ${{{{\mathcal{T}}_{{P},X}}^{{\Delta}}}\uparrow i+1} = {{{{\mathcal{T}}_{{P},X}}^{{\Delta}}}({{{{\mathcal{T}}_{{P},X}}^{{\Delta}}}\uparrow i})} = {{{{\mathcal{T}}_{{P},X}}^{{\Delta}}}\uparrow i}$ for some $i\geq 0$ , and we denote this least fixpoint by ${{{{\mathcal{T}}_{{P},X}}^{{\Delta}}}\uparrow \infty}$ . For ${\Delta}\in\{\small{GZ},\small{LPST},\small{MR},\small{DPB}\}$ , we call X a $\Delta$ -answer set of P if X is a model of P such that ${{{{\mathcal{T}}_{{P},X}}^{{\Delta}}}\uparrow \infty} = X$ .

Example 8 Reconsider the program ${P}_2$ from Example 4:

\begin{alignat}{1} \tag{$r_4$} & p \leftarrow \small{SUM}{[1:p]} > 0 \\ \tag{$r_5$} & p \leftarrow \small{SUM}{[1:p]} < 1.\end{alignat}

We have that $X=\{p\}$ is the unique model of ${P}_2$ (over $\mathcal{P}=\{p\}$ ). Then, ${\alpha(\small{SUM}{[1:p]} < 1,X)}=1$ yields $X{\not\models} {B(r_5)}$ and $(\emptyset,X) {{\not\models}_{{\Delta}}} {B(r_5)}$ for ${\Delta}\in\{\small{GZ},\small{LPST},\small{MR}\}$ . Moreover, $(\emptyset,X) {{\not\models}_{{\Delta}}} {B(r_4)}$ follows from ${\alpha(\small{SUM}{[1:p]} > 0,\emptyset)}=0$ and $\emptyset{\not\models} {B(r_4)}$ . As a consequence, for ${\Delta}\in\{\small{GZ},\small{LPST},\small{MR}\}$ , we obtain ${{{{\mathcal{T}}_{{P}_2,X}}^{{\Delta}}}\uparrow \infty}={{{{\mathcal{T}}_{{P}_2,X}}^{{\Delta}}}\uparrow 0}=\emptyset$ , so that X is not a ${\Delta}$ -answer set of ${P}_2$ .

Unlike that, $\emptyset\models {B(r_5)}$ and $X\models {B(r_4)}$ with ${H(r_5)} = {H(r_4)} = \{p\}$ lead to ${{{{\mathcal{T}}_{{P}_2,X}}^{\small{DPB}}}\uparrow \infty} = {{{{\mathcal{T}}_{{P}_2,X}}^{\small{DPB}}}\uparrow 1} = {{{{\mathcal{T}}_{{P}_2,X}}^{\small{DPB}}}(\emptyset)} = \{p\} = X$ . Hence, we conclude that X is a DPB-answer set of ${P}_2$ .

Example 9 Recall from Example 5 that $X=\{p,q\}$ is the unique model and FFLP-answer set of ${P}_1$ :

\begin{alignat}{1} \tag{$r_1$} & p \leftarrow \small{SUM}{[1:p,-1:q]} \geq 0 \\ \tag{$r_2$} & p \leftarrow \small{SUM}{[1:q]} > 0 \\ \tag{$r_3$} & q \leftarrow \small{SUM}{[1:p]} > 0.\end{alignat}

Considering the empty interpretation $\emptyset$ , we have that ${\small{AT}(A)}\cap X\neq \emptyset$ for each aggregate expression $A\in{B(r_1)}\cup{B(r_2)}\cup{B(r_3)}$ . Hence, ${{{{\mathcal{T}}_{{P}_1,X}}^{\small{GZ}}}\uparrow \infty}={{{{\mathcal{T}}_{{P}_1,X}}^{\small{GZ}}}\uparrow 0}=\emptyset$ yields that X is not a GZ-answer set of ${P}_1$ . Regarding ${{{\mathcal{T}}_{{P}_1,X}}^{\small{LPST}}}$ , observe that $\emptyset{\not\models}{B(r_2)}$ , $\emptyset{\not\models}{B(r_3)}$ , and $\{q\}{\not\models}{B(r_1)}$ in view of ${\alpha(\small{SUM}{[1:p,-1:q]} \geq 0,\{q\})}=-1$ . This means that $(\emptyset,X){{\not\models}_{\small{LPST}}} {B(r)}$ for all $r\in{P}_1$ , so that ${{{{\mathcal{T}}_{{P}_1,X}}^{\small{LPST}}}\uparrow \infty}={{{{\mathcal{T}}_{{P}_1,X}}^{\small{LPST}}}\uparrow 0}=\emptyset$ disproves X to be an LPST-answer set of ${P}_1$ .

When we turn to ${{{\mathcal{T}}_{{P}_1,X}}^{\small{MR}}}$ , then ${\alpha(\small{SUM}{[1:p,-1:q]} \geq 0,\emptyset)} = {\alpha(\small{SUM}{[1:p,-1:q]} \geq 0,X)} = 0$ shows that $(\emptyset,X){\models_{\small{MR}}}{B(r_1)}$ and ${{{{\mathcal{T}}_{{P}_1,X}}^{\small{MR}}}\uparrow 1} = {{{{\mathcal{T}}_{{P}_1,X}}^{\small{MR}}}(\emptyset)} = \{p\}$ . Given that $(\{p\},X){\models_{\small{MR}}}{B(r_3)}$ , this leads on to ${{{{\mathcal{T}}_{{P}_1,X}}^{\small{MR}}}\uparrow \infty} = {{{{\mathcal{T}}_{{P}_1,X}}^{\small{MR}}}\uparrow 2} = {{{{\mathcal{T}}_{{P}_1,X}}^{\small{MR}}}(\{p\})} = \{p,q\} = X$ , from which we conclude that X is an MR-answer set of ${P}_1$ .

For obtaining the least fixpoint of ${{{\mathcal{T}}_{{P}_1,X}}^{\small{DPB}}}$ , consider the rules $r_1$ and $r_2$ , and observe that $\emptyset\models {B(r_1)}$ , $\{p\}\models {B(r_1)}$ , $\{q\}\models {B(r_2)}$ , and $X\models {B(r_1)}$ as well as $X\models {B(r_2)}$ . That is, for each interpretation $Z\subseteq X$ , the body of some rule with p in the head is satisfied by Z. Hence, we get ${{{{\mathcal{T}}_{{P}_1,X}}^{\small{DPB}}}\uparrow 1} = {{{{\mathcal{T}}_{{P}_1,X}}^{\small{DPB}}}(\emptyset)} = \{p\}$ , which in view of $\{p\}\models {B(r_3)}$ and $X\models {B(r_3)}$ brings us further to ${{{{\mathcal{T}}_{{P}_1,X}}^{\small{DPB}}}\uparrow \infty} = {{{{\mathcal{T}}_{{P}_1,X}}^{\small{DPB}}}\uparrow 2} = {{{{\mathcal{T}}_{{P}_1,X}}^{\small{DPB}}}(\{p\})} = \{p,q\} = X$ . This means that X is also a DPB-answer set of ${P}_1$ .

Let us modify the program ${P}_1$ to ${P}_1'$ over $\mathcal{P}=\{p,q,s\}$ , in which $r_1$ and $r_3$ are replaced by:

\begin{alignat}{1} \tag{$r_1'$} & s \leftarrow \small{SUM}{[1:p,-1:q]} \geq 0 \\ \tag{$r_3'$} & q \leftarrow \small{SUM}{[1:s]} > 0.\end{alignat}

Intuitively, rule $r_1'$ requires s true if p is true or q is false, and rule $r_3'$ requires q true if s is true (recall that $r_2$ requires p true if q is true). One can check that $X'=\{p,q,s\}$ is the unique model as well as an FFLP- and MR-answer set of ${P}_1'$ . Turning again to ${{{\mathcal{T}}_{{P}_1',X'}}^{\small{DPB}}}$ , we have that $\emptyset{\not\models} {B(r_2)}$ , $\emptyset{\not\models} {B(r_3')}$ , $\{q\}{\not\models} {B(r_1')}$ , $\{q\}{\not\models} {B(r_3')}$ , and the heads of $r_1'$ and $r_2$ are disjoint for the modified program ${P}_1'$ . (Each interpretation $Z'\subseteq X'$ is such that $Z'\models {B(r_1')}$ or $Z'\models {B(r_2)}$ , yet ${H(r_1')}\cap {H(r_2)} = \{s\} \cap \{p\} = \emptyset$ .) Given these considerations, we conclude that ${{{{\mathcal{T}}_{{P}_1',X'}}^{\small{DPB}}}\uparrow \infty} = {{{{\mathcal{T}}_{{P}_1',X'}}^{\small{DPB}}}\uparrow 0} = \emptyset$ , so that ${P}_1'$ does not have any DPB-answer set. This shows that FFLP-answer sets are not necessarily DPB-answer sets as well.

Example 10 In Example 6, we have checked that $X=\{y_1,x_2,z_1,z_2,p\}$ is the unique FFLP-answer set of ${P}_3$ :

\begin{alignat}{1} \tag{$r_6$} & x_1 \leftarrow \small{SUM}{[1:y_1]} < 1 \\ \tag{$r_7$} & y_1 \leftarrow \small{SUM}{[1:x_1]} < 1 \\ \tag{$r_8$} & x_2 \leftarrow \small{SUM}{[1:y_2]} < 1 \\ \tag{$r_9$} & y_2 \leftarrow \small{SUM}{[1:x_2]} < 1 \\ \tag{$r_{10}$} & z_1 \leftarrow \small{SUM}{[1:p]} > 0 \\ \tag{$r_{11}$} & z_2 \leftarrow \small{SUM}{[1:p]} > 0 \\ \tag{$r_{12}$} & p \leftarrow \small{SUM}{[1:y_1,2:y_2,2:z_1,3:z_2]} \neq 5 \\ \tag{$r_{13}$} & \bot \leftarrow \small{SUM}{[1:p]} < 1.\end{alignat}

Inspecting ${{{\mathcal{T}}_{{P}_3,X}}^{\small{GZ}}}$ , we get ${{{{\mathcal{T}}_{{P}_3,X}}^{\small{GZ}}}\uparrow 1} = {{{{\mathcal{T}}_{{P}_3,X}}^{\small{GZ}}}(\emptyset)} = \{y_1,x_2\}$ because $X\models {B(r_7)}$ , $X\models {B(r_8)}$ , and ${\small{AT}(\small{SUM}{[1:x_1]} < 1)}\cap X = {\small{AT}(\small{SUM}{[1:y_2]} < 1)}\cap X = \emptyset$ . Given that $X{\not\models} {B(r_6)}$ , $X{\not\models} {B(r_9)}$ , ${\small{AT}(\small{SUM}{[1:p]} > 0)}\cap \{y_1,x_2\} = \emptyset \neq \{p\} = {\small{AT}(\small{SUM}{[1:p]} > 0)}\cap X$ , and ${\small{AT}(\small{SUM}{[1:y_1, 2:y_2, 2:z_1, 3:z_2]} \neq 5)}\cap \{y_1,x_2\} = \{y_1\} \neq \{y_1,z_1,z_2\} = {\small{AT}(\small{SUM}{[1:y_1,2:y_2,2:z_1,3:z_2]} \neq 5)}\cap X,$ , we obtain ${{{{\mathcal{T}}_{{P}_3,X}}^{\small{GZ}}}\uparrow \infty} = {{{{\mathcal{T}}_{{P}_3,X}}^{\small{GZ}}}\uparrow 1} = \{y_1,x_2\}$ , so that X is not a GZ-answer set of ${P}_3$ .

For ${\Delta}\in\{\small{LPST},\small{DPB}\}$ , we also have that ${{{{\mathcal{T}}_{{P}_3,X}}^{{\Delta}}}\uparrow 1} = {{{{\mathcal{T}}_{{P}_3,X}}^{{\Delta}}}(\emptyset)} = \{y_1,x_2\}$ , as $Z\models {B(r_7)}$ and $Z\models {B(r_8)}$ for each $Z\subseteq X$ , while the interpretation $\{z_1,z_2\}\subseteq X$ is such that $\{z_1,z_2\}{\not\models} \small{SUM}{[1:p]} > 0$ and $\{z_1,z_2\}{\not\models} \small{SUM}{[1:y_1,2:y_2,2:z_1,3:z_2]} \neq 5$ . However, $Z\models \small{SUM}{[1:y_1, 2:y_2, 2:z_1, 3:z_2]} \neq 5$ is the case for every $\{y_1,x_2\}\subseteq Z\subseteq X$ , which leads to ${{{{\mathcal{T}}_{{P}_3,X}}^{{\Delta}}}\uparrow 2} = {{{{\mathcal{T}}_{{P}_3,X}}^{{\Delta}}}(\{y_1,x_2\})} = \{y_1,x_2,p\}$ . Then, $Z\models \small{SUM}{[1:p]} > 0$ , for any interpretation $\{y_1,x_2,p\}\subseteq Z$ , yields ${{{{\mathcal{T}}_{{P}_3,X}}^{{\Delta}}}\uparrow \infty} = {{{{\mathcal{T}}_{{P}_3,X}}^{{\Delta}}}\uparrow 3} = {{{{\mathcal{T}}_{{P}_3,X}}^{{\Delta}}}(\{y_1,x_2,p\})} = \{y_1,x_2,z_1,z_2,p\}=X$ , which shows that X is an LPST- and a DPB-answer set of ${P}_3$ .

Regarding ${{{\mathcal{T}}_{{P}_3,X}}^{\small{MR}}}$ , in view of $X\models \small{SUM}{[1:y_1, 2:y_2, 2:z_1, 3:z_2]} \neq 5$ and ${\alpha(\small{SUM}{[1:y_1, 2:y_2, 2:z_1, 3:z_2]} \neq 5,\emptyset)} = 0$ , we get ${{{{\mathcal{T}}_{{P}_3,X}}^{\small{MR}}}\uparrow 1} = {{{{\mathcal{T}}_{{P}_3,X}}^{\small{MR}}}(\emptyset)} = \{y_1,x_2,p\}$ in the first step, and then ${{{{\mathcal{T}}_{{P}_3,X}}^{\small{MR}}}\uparrow \infty} = {{{{\mathcal{T}}_{{P}_3,X}}^{\small{MR}}}\uparrow 2} = {{{{\mathcal{T}}_{{P}_3,X}}^{\small{MR}}}(\{y_1,x_2,p\})} = \{y_1,x_2,z_1,z_2,p\}=X$ . On the one hand, this means that X is an MR-answer set of ${P}_3$ . On the other hand, the interpretations $X_2=\{x_1,y_2,z_1,z_2,p\}$ and $X_4=\{y_1,y_2,z_1,z_2,p\}$ (according to the naming scheme of Example 6) are obtained as additional MR-answer sets of ${P}_3$ that are not backed up by any of the other semantics. In fact, counting on the existence of some interpretation $Z \subseteq {{{{\mathcal{T}}_{{P},X}}^{\small{MR}}}\uparrow i}$ such that $Z\models A$ , for an aggregate expression A belonging to the body of a rule $r\in {P}$ , to proceed with (potentially) adding H(r) to ${{{{\mathcal{T}}_{{P},X}}^{\small{MR}}}\uparrow i}$ disregards the satisfaction of A by ${{{{\mathcal{T}}_{{P},X}}^{\small{MR}}}\uparrow i}$ itself as well as interpretations extending it. For this reason, Vanbesien et al. (Reference Vanbesien, Bruynooghe and Denecker2021) classify ${{{\mathcal{T}}_{{P},X}}^{\small{MR}}}$ as not well-behaved, while ${{{\mathcal{T}}_{{P},X}}^{{\Delta}}}$ is well-behaved for ${\Delta}\in\{\small{GZ},\small{LPST},\small{DPB}\}$ .

The programs considered in Example 8–10 did not have GZ-answer sets because of the strong condition ${\small{AT}(A)}\cap Y = {\small{AT}(A)}\cap X$ for $(Y,X){\models_{\small{GZ}}} A$ . Its intention is to circumvent so-called vicious circles (Gelfond and Zhang Reference Gelfond and Zhang2019), where the satisfaction of an aggregate expression A has some influence on the outcome of the aggregation function in A, which happens in Example 8–10, for example, with the rule $p \leftarrow \small{SUM}{[1:p,-1:q]} \geq 0$ to conclude p from an aggregate expression mentioning p.

To make circularity more formal, for a program P, let ${{\mathcal{G}}_{{P}}}=(\mathcal{P},\{(p,q) \mid r\in{P}, p\in{H(r)}, A\in{B(r)}, q\in{\small{AT}(A)}\})$ be the (directed) atom dependency graph of P. If ${{\mathcal{G}}_{{P}}}$ is acyclic (and the rules in P are non-disjunctive), one can show that there is at most one ${\Delta}$ -answer set of P, for ${\Delta}\in\{{FFLP},\small{GZ},\small{LPST},\small{MR},\small{DPB}\}$ , and that all aggregate semantics under consideration coincide. Provided that P does not include constraints, acyclicity of ${{\mathcal{G}}_{{P}}}$ is sufficient for the existence of a GZ-answer set of P. However, such acyclicity is not a necessary condition, for example, GZ-answer sets match standard answer sets (Gelfond and Lifschitz Reference Gelfond, Lifschitz, Kowalski and Bowen1988) when aggregate expressions of the form $\small{SUM}{[1:p]}>0$ or $\small{SUM}{[1:p]}<1$ replace (negated) propositional atoms p, no matter whether ${{\mathcal{G}}_{{P}}}$ is acyclic or not, and this correspondence applies to all but the DPB-answer set semantics (cf. Example 8). In fact, vicious circles are not identified syntactically, but rather the construction of a GZ-answer set X of P by ${{{\mathcal{T}}_{{P},X}}^{\small{GZ}}}$ witnesses the non-circular provability of all atoms in X.

Example 11 Consider the program ${P}_4$ , which constitutes a propositional version of the company controls problem encoding introduced in Section 1 for the instance given in Figure 2:

\begin{alignat}{1} \tag{$r_{14}$} & o_{a,b} \leftarrow \top \\ \tag{$r_{15}$} & o_{a,c} \leftarrow \top \\ \tag{$r_{16}$} & o_{b,c} \leftarrow \top \\ \tag{$r_{17}$} & c_{a,b} \leftarrow \small{SUM}{[80: o_{a,b}]} > 50 \\ \tag{$r_{18}$} & c_{a,c} \leftarrow \small{SUM}{[30: o_{a,c}, 30: c_{a,b}]} > 50 \\ \tag{$r_{19}$} & c_{b,c} \leftarrow \small{SUM}{[30: o_{b,c}, 30: c_{b,a}]} > 50.\end{alignat}

The atom dependency graph ${{\mathcal{G}}_{{P}_4}}=(\{o_{a,b},o_{a,c},o_{b,c},c_{a,b},c_{a,c},c_{b,a},c_{b,c}\}, \{(c_{a,b},o_{a,b}), (c_{a,c},o_{a,c}), (c_{a,c},c_{a,b}), (c_{b,c},o_{b,c}), (c_{b,c},c_{b,a})\})$ , shown in Figure 4, is acyclic, and the interpretation $X=\{o_{a,b},o_{a,c},o_{b,c},c_{a,b},c_{a,c}\}$ is a model of ${P}_4$ . Let us construct ${{{{\mathcal{T}}_{{P}_4,X}}^{\small{GZ}}}\uparrow \infty}$ to check that X is a GZ-answer set of ${P}_4$ . In the first step, $(\emptyset,X){\models_{\small{GZ}}}{B(r)}$ applies for the facts $r\in\{r_{14},r_{15},r_{16}\}$ , so that ${{{{\mathcal{T}}_{{P}_4,X}}^{\small{GZ}}}\uparrow 1} = {{{{\mathcal{T}}_{{P}_4,X}}^{\small{GZ}}}(\emptyset)} = \{o_{a,b}, o_{a,c}, o_{b,c}\}$ . Then, we have that ${\small{AT}(\small{SUM}{[80: o_{a,b}]} > 50)}\cap {{{{\mathcal{T}}_{{P}_4,X}}^{\small{GZ}}}\uparrow 1} = {\small{AT}(\small{SUM}{[80: o_{a,b}]} > 50)}\cap X = \{o_{a,b}\}$ , and $X\models {B(r_{17})}$ in view of ${\alpha(\small{SUM}{[80: o_{a,b}]} > 50,X)}=80$ . We thus get ${{{{\mathcal{T}}_{{P}_4,X}}^{\small{GZ}}}\uparrow 2} = {{{{\mathcal{T}}_{{P}_4,X}}^{\small{GZ}}}(\{o_{a,b}, o_{a,c}, o_{b,c}\})} = \{o_{a,b}, o_{a,c}, o_{b,c}, c_{a,b}\}$ , and ${\small{AT}(\small{SUM}{[30: o_{a,c}, 30: c_{a,b}]} > 50)}\cap {{{{\mathcal{T}}_{{P}_4,X}}^{\small{GZ}}}\uparrow 2} = {\small{AT}(\small{SUM}{[30: o_{a,c}, 30: c_{a,b}]} > 50)}\cap X = \{o_{a,c}, c_{a,b}\}$ along with ${\alpha(\small{SUM}{[30: o_{a,c}, 30: c_{a,b}]} > 50,X)}=60$ and $X\models {B(r_{18})}$ lead to ${{{{\mathcal{T}}_{{P}_4,X}}^{\small{GZ}}}\uparrow 3} = {{{{\mathcal{T}}_{{P}_4,X}}^{\small{GZ}}}(\{o_{a,b}, o_{a,c}, o_{b,c}, c_{a,b}\})} = \{o_{a,b}, o_{a,c}, o_{b,c}, c_{a,b}, c_{a,c}\} = X$ . Given that $X{\not\models} {B(r_{19})}$ , the least fixpoint ${{{{\mathcal{T}}_{{P}_4,X}}^{\small{GZ}}}\uparrow \infty} = {{{{\mathcal{T}}_{{P}_4,X}}^{\small{GZ}}}\uparrow 3} = X$ yields that X is a GZ-answer set of ${P}_4$ .

Fig. 4. Dependency graph of program ${P}_4$ from Example 11.

Fig. 5. Relationships between aggregate semantics, where an arc indicates that answer sets carry forward from the origin to the target semantics for non-disjunctive programs with monotone (arc label $+$ ), anti-monotone (arc label $-$ ), convex (arc label $\pm$ ), or arbitrary (no arc label) aggregate expressions, respectively.

However, note that X is no longer a GZ-answer set of ${P}_4'$ , obtained by replacing r ₁₇ with

\begin{alignat}{1} \tag{$r_{17}'$} & c_{a,b} \leftarrow \small{SUM}{[80: o_{a,b}, w: c_{a,c}]} > 50\end{alignat}

for some weight $w\geq 0$ . While we still obtain ${{{{\mathcal{T}}_{{P}_4',X}}^{\small{GZ}}}\uparrow 1} = {{{{\mathcal{T}}_{{P}_4',X}}^{\small{GZ}}}(\emptyset)} = \{o_{a,b}, o_{a,c}, o_{b,c}\}$ , we end up with ${{{{\mathcal{T}}_{{P}_4',X}}^{\small{GZ}}}\uparrow \infty} = {{{{\mathcal{T}}_{{P}_4',X}}^{\small{GZ}}}\uparrow 1}$ because ${\small{AT}(\small{SUM}{[80: o_{a,b}, w: c_{a,c}]} > 50)}\cap {{{{\mathcal{T}}_{{P}_4',X}}^{\small{GZ}}}\uparrow 1} = \{o_{a,b}\} \neq \{o_{a,b}, c_{a,c}\}= {\small{AT}(\small{SUM}{[80: o_{a,b}, w: c_{a,c}]} > 50)}\cap X$ and thus $({{{{\mathcal{T}}_{{P}_4',X}}^{\small{GZ}}}\uparrow 1},X){{\not\models}_{\small{GZ}}} {B(r_{17}')}$ . That is, X is rejected as a $\small{GZ}$ -answer set of ${P}_4'$ in view of the circularity between $c_{a,b}$ and $c_{a,c}$ , which are involved in aggregate expressions in the bodies of $r_{17}'$ and $r_{18}$ . When considering standard answer sets of programs without (sophisticated) aggregates (Gelfond and Lifschitz Reference Gelfond, Lifschitz, Kowalski and Bowen1988; Gelfond and Lifschitz Reference Gelfond and Lifschitz1991), circular rules alone do not yield provability of atoms in their heads. Unlike that, not all propositional atoms subject to an aggregation function may be needed to satisfy a respective aggregate expression, so that rejecting any circularity is a very strong condition for programs with aggregates. In fact, without going into the details, we have that X is the unique ${\Delta}$ -answer set of both ${P}_4$ and ${P}_4'$ for ${\Delta}\in\{\small{FFLP},\small{LPST},\small{MR},\small{DPB}\}$ , that is, all aggregate semantics other than GZ.

3.3 Semantic relationships

As mentioned above, the satisfaction relation ${\models_{\small{GZ}}}$ is a subset of ${\models_{\small{LPST}}}$ , which is in turn a subset of ${\models_{\small{MR}}}$ . That is, given a model X of a (non-disjunctive) program P, we immediately get ${{{{\mathcal{T}}_{{P},X}}^{\small{LPST}}}\uparrow \infty} = X$ from ${{{{\mathcal{T}}_{{P},X}}^{\small{GZ}}}\uparrow \infty} = X$ , and ${{{{\mathcal{T}}_{{P},X}}^{\small{MR}}}\uparrow \infty} = X$ from ${{{{\mathcal{T}}_{{P},X}}^{\small{LPST}}}\uparrow \infty} = X$ , which means that a GZ-answer set X of P is an LPST-answer set as well, and an LPST-answer set X of P also an MR-answer set. The converse relationships do not apply in general, yet may come into effect for programs restricted to monotone, anti-monotone, or convex aggregate expressions only. Moreover, the question arises how DPB-answer sets determined by the operator ${{{\mathcal{T}}_{{P},X}}^{\small{DPB}}}$ and model-based FFLP-answer sets relate to the other aggregate semantics. A part of these relationships have already been studied by Ferraris (Reference Ferraris2011) and Liu et al. (Reference Liu, Pontelli, Son and TruszczyŃski2010), and in the following we give a complete account for the aggregate semantics under consideration, assuming programs in question to be non-disjunctive.

Figure 4 and Table 1 visualize the relationships between different aggregate semantics, where arcs without label express that answer sets under one semantics are preserved by another semantics for programs with arbitrary, that is, possibly non-convex, aggregate expressions. The restriction of such a correspondence to programs with convex, monotone, or anti-monotone aggregate expressions only is indicated by the arc label $\pm$ , $+$ , or $-$ , respectively. Transitive relationships, for example, the fact that each GZ-answer set is an MR-answer set as well, are not stated by explicit arcs for better readability. A summary of the logic programs used to illustrate the similarities and differences between the aggregate semantics in Sections 3.1 and 3.2 is given in Table 2.

Table 1. Relationships between semantics for non-disjunctive programs with (monotone, anti-monotone, convex, or arbitrary) aggregate expressions, showing when Monotonicity conditions guaranteeing answer sets according to the semantics in rows to be answer sets according to the semantics in columns

Table 2 Summary of examples showing differences between aggregate semantics, where $X = \{o_{a,b},o_{a,c},o_{b,c},c_{a,b},c_{a,c}\}$

Table 3. Computational complexity of the Exist and Check reasoning tasks for different aggregate semantics and the monotonicity of aggregate expressions included in non-disjunctive programs, where cases in which elevated complexity relies on the NP-hardness of deciding whether aggregate expressions under consideration are satisfiable are indicated by lower complexity classes obtained with tractable satisfiability checks in parentheses

The most restrictive semantics is obtained with GZ-answer sets, in the sense that the fewest models X of a program P pass the construction by means of ${{{\mathcal{T}}_{{P},X}}^{\small{GZ}}}$ . As ${{{\mathcal{T}}_{{P},X}}^{\small{LPST}}}$ relaxes the conditions for concluding head atoms, LPST-answer sets are guaranteed to include GZ-answer sets, as indicated by an arc without label in Figure 4. The observation that $(Y,X){\models_{\small{LPST}}} {B(r)}$ , for some rule $r\in{P}$ and $Y\subseteq X$ , implies $Z\models {B(r)}$ for every interpretation $Y\subseteq Z\subseteq X$ yields that ${H(r)}\subseteq {{{{\mathcal{T}}_{{P},X}}^{\small{DPB}}}(Y)}$ , so that each LPST-answer set X of P is a DPB-answer set as well. Moreover, when $Y\subset X$ for an LPST-answer set X of P, the fact that ${{{{\mathcal{T}}_{{P},X}}^{\small{LPST}}}(Y)}\nsubseteq Y$ shows that Y is not a model of the reduct ${{P}^{X}}$ , which in turn witnesses that X is a $\subseteq$ -minimal model of ${{P}^{X}}$ and thus an FFLP-answer set of P. The last general relationship that applies for programs with arbitrary aggregate expressions expresses that each FFLP-answer set X of P is also an MR-answer set, given that $Y{\not\models} {{P}^{X}}$ , for any interpretation $Y\subset X$ , implies that ${{{{\mathcal{T}}_{{P},X}}^{\small{MR}}}(Y)}\nsubseteq Y$ . As discussed in Examples 8 and 9, FFLP- and DPB-answer sets can be mutually distinct, so that no (transitive) general relationship is obtained between these two aggregate semantics.

Considering relationships for convex, monotone, or anti-monotone aggregate expressions, an MR-answer set X of P is also an LPST-answer set when the program P includes convex aggregate expressions only. This follows from the observation that, for a convex aggregate expression A and each interpretation $Y\subseteq X$ , the conditions $X\models A$ and $Z\models A$ , for some $Z\subseteq Y$ , of $(Y,X){\models_{\small{MR}}} A$ yield the condition of $(Y,X){\models_{\small{LPST}}} A$ that $Z\models A$ for every $Y\subseteq Z\subseteq X$ . The general relationship between LPST- and FFLP-answer sets then further implies that X is an FFLP-answer set of P as well, so that FFLP-, LPST-, and MR-answer sets coincide for programs with convex aggregate expressions only. For establishing similar correspondences to DPB-answer sets, as Example 8 shows, programs with convex or both monotone and anti-monotone aggregate expressions, respectively, are still too general. However, when the aggregate expressions in a program P are monotone or anti-monotone only, for interpretations $Y\subseteq X$ , the intersection over all $Y\subseteq Z\subseteq X$ taken by ${{{{\mathcal{T}}_{{P},X}}^{\small{DPB}}}(Y)}$ collapses to checking whether rule bodies are satisfied by Y or X, respectively, while satisfaction by other interpretations Z is a consequence of (anti-)monotonicity. Hence, we have that ${{{{\mathcal{T}}_{{P},X}}^{\small{LPST}}}(Y)}={{{{\mathcal{T}}_{{P},X}}^{\small{DPB}}}(Y)}$ , which means that each DPB-answer set X of P is also an LPST-answer set in case of monotone or anti-monotone aggregate expressions only. By (transitive) general relationships, this correspondence carries forward to FFLP- and MR-answer sets.

Interestingly, GZ-answer sets do not correspond to the other semantics even for programs whose aggregate expressions are restricted to be monotone. For instance, the program P consisting of the rule $p \leftarrow \small{SUM}{[1:p]} \geq 0$ , which includes the monotone as well as anti-monotone aggregate expression $\small{SUM}{[1:p]} \geq 0$ , has $\{p\}$ as an answer set under all aggregate semantics but GZ, where the latter is due to ${{{{\mathcal{T}}_{{P},\{p\}}}^{\small{GZ}}}\uparrow \infty}={{{{\mathcal{T}}_{{P},\{p\}}}^{\small{GZ}}}\uparrow 0}=\emptyset$ in view of ${\small{AT}(\small{SUM}{[1:p]} \geq 0)}\cap \{p\}\neq \emptyset$ . As $\{p\}$ is the unique model of P, this means that P does not have any GZ-answer set, even though P includes only one aggregate expression that is both monotone and anti-monotone. Such a behavior is justified by Gelfond and Zhang (Reference Gelfond and Zhang2019) by a more uniform treatment of recursive symbolic rules like the following:

In fact, a program consisting of the second rule above, would be instantiated as

\begin{alignat*}{1} & p \leftarrow \small{SUM}{[1: p]} = 0\\ & p \leftarrow \small{SUM}{[1: p]} = 1\end{alignat*}

which has no answer sets according to all semantics discussed in this paper.

4.1 Answer set checking

Starting with Check for (non-disjunctive) programs P including monotone or anti-monotone aggregate expressions only, we have that the task stays in P for all aggregate semantics. An intuitive explanation is that all but the GZ-answer set semantics coincide for such programs and that a construction, for example, by means of ${{{{\mathcal{T}}_{{P},X}}^{\small{DPB}}}(Y)}$ , for some $Y\subseteq X$ , can focus on concluding head atoms of rules $r\in{P}$ such that $Y\models {B(r)}$ or $X\models {B(r)}$ , respectively. For ${{{{\mathcal{T}}_{{P},X}}^{\small{GZ}}}(Y)}$ , also the additional condition ${\small{AT}(A)}\cap Y = {\small{AT}(A)}\cap X$ needs to be checked for each aggregate expression $A\in{B(r)}$ . Regardless of the particular semantics, all relevant checks can be accomplished in polynomial time: $X\models {P}$ to make sure that X is a model of P, $Y\models {B(r)}$ or $X\models {B(r)}$ for rules $r\in{P}$ , and possibly ${\small{AT}(A)}\cap Y = {\small{AT}(A)}\cap X$ for aggregate expressions $A\in{B(r)}$ . The strong condition ${\small{AT}(A)}\cap Y = {\small{AT}(A)}\cap X$ for $(Y,X){\models_{\small{GZ}}} A$ also circumvents elevated complexity of Check under GZ-answer set semantics when turning to programs with convex or arbitrary, that is, possibly non-convex, aggregate expressions.

In case of convex aggregate expressions, which include monotone as well as anti-monotone aggregate expressions, the Check task remains tractable for ${\Delta}\in\{\small{FFLP},\small{LPST},\small{MR}\}$ , given that the three semantics coincide, and for an aggregate expression A, checking $Y\models A$ and $X\models A$ is sufficient to conclude that $(Y,X){\models_{\small{LPST}}} A$ as well as $(Y,X){\models_{\small{MR}}} A$ . Unlike that, Check becomes more complex, that is, coNP-complete, for DPB-answer sets of programs with convex aggregate expressions, where Denecker et al. (Reference Denecker, Marek and TruszczyŃski2004) show coNP-hardness by reduction from deciding whether a propositional formula in disjunctive normal form is a tautology. Notably, the logic program given in this reduction does not refer to (sophisticated) aggregates, and the simultaneous availability of monotone and anti-monotone aggregate expressions of the form $\small{SUM}{[1:p]}>0$ or $\small{SUM}{[1:p]}<1$ to express (negated) propositional atoms p is already sufficient. This complexity does also not increase any further in the presence of non-convex aggregate expressions, as for disproving X to be a DPB-answer set of P, it is sufficient to check that $X{\not\models} {P}$ , or otherwise to determine a collection of (not necessarily distinct) interpretations $Y_1\subseteq X,\dots,Y_{|X|}\subseteq X$ such that $Z\subseteq Y$ and $Z\subset X$ hold for $Y= Y_1\cap \dots\cap Y_{|X|}$ and

\begin{alignat*}{1} Z=\left( \mbox{$\bigcup$}_{r\in{P},Y_1 \models{B(r)}}{H(r)} \right)\cap \dots\cap \left( \mbox{$\bigcup$}_{r\in{P},Y_{|X|}\models{B(r)}}{H(r)} \right)\cap X\text{.}\end{alignat*}

In the latter case, we have that ${{{{\mathcal{T}}_{{P},X}}^{\small{DPB}}}(Y)}\subseteq Y$ and ${{{{\mathcal{T}}_{{P},X}}^{\small{DPB}}}(Y)}\subset X$ for $Y = Y_1\cap \dots\cap Y_{|X|}\subseteq X$ , which in turn implies that ${{{{\mathcal{T}}_{{P},X}}^{\small{DPB}}}\uparrow \infty}\subseteq{{{{\mathcal{T}}_{{P},X}}^{\small{DPB}}}(Y)}\subset X$ . Moreover, when ${{{{\mathcal{T}}_{{P},X}}^{\small{DPB}}}\uparrow \infty}\subset X$ , note that at most $|X\setminus{{{{\mathcal{T}}_{{P},X}}^{\small{DPB}}}\uparrow \infty}|\leq |X|$ many interpretations ${{{{\mathcal{T}}_{{P},X}}^{\small{DPB}}}\uparrow \infty}\subseteq Y\subseteq X$ are needed to show that none of the atoms in $X\setminus{{{{\mathcal{T}}_{{P},X}}^{\small{DPB}}}\uparrow \infty}$ belongs to ${{{{\mathcal{T}}_{{P},X}}^{\small{DPB}}}({{{{\mathcal{T}}_{{P},X}}^{\small{DPB}}}\uparrow \infty})}$ , so that Check under DPB-answer set semantics stays in coNP for programs with arbitrary aggregate expressions.

For ${\Delta}\in\{\small{FFLP},\small{LPST},\small{MR}\}$ , arbitrary aggregate expressions make a difference regarding the complexity of the Check task. Concerning FFLP-answer sets, membership in coNP is immediate as checking that $X{\not\models} {P}$ or $Y\models {{P}^{X}}$ , for some $Y\subset X$ , is tractable. The coNP-hardness can be established by a reduction from disjunctive programs to programs with nested implications due to Ferraris (Reference Ferraris2011), which replaces a disjunctive rule like $p\vee q\leftarrow \top$ by two rules $p\leftarrow \underline{(p\leftarrow q)}$ and $q\leftarrow \underline{(q\leftarrow p)}$ . (Note that rule bodies with nested implications are underlined to avoid any ambiguity with rules.) These nested implications are satisfied by the empty interpretation $\emptyset$ , become unsatisfied by $\{q\}$ or $\{p\}$ , respectively, and are satisfied by the remaining interpretations, in particular, the extended interpretation $\{p,q\}$ . Such satisfaction can in turn be captured in terms of non-convex aggregate expressions like $\small{SUM}{[1:p,-1:q]}\geq 0$ and $\small{SUM}{[-1:p,1:q]}\geq 0$ for $\underline{(p\leftarrow q)}$ or $\underline{(q\leftarrow p)}$ , respectively, and various other representations, for example, $\small{MAX}{[1:p,-1:q]}\neq -1$ or $\small{AVG}{[0:x,-1:p,1:q]}\geq 0$ , where $x\leftarrow \top$ is used as an auxiliary fact, yield the same effect. This shows that Check under FFLP-answer set semantics is coNP-complete for programs including non-convex aggregate expressions (Alviano and Faber Reference Alviano, Faber, Cabalar and Son2013).

Turning to LPST-answer sets, an interpretation $Y\subset X$ disproves a model X of P to be an LPST-answer set of P, if for each rule $r\in{P}$ with ${H(r)}\nsubseteq Y$ , we find an aggregate expression $A\in{B(r)}$ along with some $Y\subseteq Z\subseteq X$ such that $Z{\not\models} A$ . As the problem of checking the existence of such a counterexample Y belongs to NP, the complementary Check task for LPST-answer sets is a member of coNP. The coNP-hardness though depends on the complexity of deciding whether $(Y,X){\models_{\small{LPST}}} A$ for an aggregate expression A, which is intractable if and only if deciding the satisfiability of the complement of A, obtainable by inverting the comparison operator of A, for example, $\small{AGG}{[w_1:p_1,\dots,w_n:p_n]}={w_0}$ when A is of the form $\small{AGG}{[w_1:p_1,\dots,w_n:p_n]}\neq{w_0}$ , is NP-complete. As discussed in Section 2.2, such elevated complexity applies to $\small{AGG}\in\{\small{SUM}, \small{TIMES}, \small{AVG}\}$ in combination with the (complementary) comparison operator $=$ . Hence, Check for LPST-answer sets is only coNP-complete when P includes aggregate expressions $\small{AGG}{[w_1:p_1, \dots, w_n:p_n]}\neq{w_0}$ with $\small{AGG}\in\{\small{SUM}, \small{TIMES}, \small{AVG}\}$ , while it drops to P otherwise, even in the presence of other forms of non-convex aggregate expressions like $\small{AVG}{[w_1:p_1, \dots, w_n:p_n]}\geq{w_0}$ or $\small{MIN}{[w_1:p_1, \dots, w_n:p_n]}\neq{w_0}$ .

Example 12 Consider the program ${P}_5$ as follows:

\begin{alignat}{1} \tag{$r_{20}$} & x_1 \leftarrow \small{SUM}{[1:p]} > 0 \\ \tag{$r_{21}$} & x_2 \leftarrow \small{SUM}{[1:p]} > 0 \\ \tag{$r_{22}$} & x_3 \leftarrow \small{SUM}{[1:p]} > 0 \\ \tag{$r_{23}$} & p \leftarrow \small{SUM}{[2 : x_1, 2 : x_2, 3 : x_3]} \neq 5\end{alignat}

For deciding whether the interpretation $X=\{x_1,x_2,x_3,p\}$ is an LPST-answer set of ${P}_5$ , starting from ${{{{\mathcal{T}}_{{P}_5,X}}^{\small{LPST}}}\uparrow 0}=\emptyset$ , we need to check the condition of $(\emptyset,X){\models_{\small{LPST}}} {B(r_{23})}$ that $Z\models \small{SUM}{[2 : x_1, 2 : x_2, 3 : x_3]} \neq 5$ for every $Z\subseteq X$ . This condition fails if and only if the complementary aggregate expression $A = \small{SUM}{[2 : x_1, 2 : x_2, 3 : x_3]} = 5$ is satisfiable, that is, when ${\alpha(A,Z)} = 5$ for some $Z\subseteq X$ . As $Z_1=\{x_1,x_3\}$ and $Z_2=\{x_2,x_3\}$ are such that ${\alpha(A,Z_1)} = {\alpha(A,Z_2)} = 5$ , the complementary aggregate expression A is satisfiable, so that $(\emptyset,X){{\not\models}_{\small{LPST}}} {B(r_{23})}$ and ${{{{\mathcal{T}}_{{P}_5,X}}^{\small{LPST}}}\uparrow \infty}={{{{\mathcal{T}}_{{P}_5,X}}^{\small{LPST}}}\uparrow 0}=\emptyset$ disproves X to be an LPST-answer set of ${P}_5$ .

When we replace the rule r ₂₃ by

\begin{alignat}{1} \tag{$r_{23}'$} & p \leftarrow \small{SUM}{[2 : x_1, 2 : x_2, 3 : x_3]} \neq 6\end{alignat}

to obtain ${P}_5'$ , there is no interpretation $Z\subseteq X$ such that ${\alpha(\small{SUM}{[2 : x_1, 2 : x_2, 3 : x_3]} = 6,Z)} = 6$ . In turn, we have that $Z\models \small{SUM}{[2 : x_1, 2 : x_2, 3 : x_3]} \neq 6$ for every $Z\subseteq X$ , which means that the condition of $(\emptyset,X){\models_{\small{LPST}}} {B(r_{23}')}$ applies and ${{{{\mathcal{T}}_{{P}_5',X}}^{\small{LPST}}}\uparrow 1}={{{{\mathcal{T}}_{{P}_5',X}}^{\small{LPST}}}(\emptyset)}=\{p\}$ . Given that ${\alpha(\small{SUM}{[1:p]} > 0, Z)}=1$ for all interpretations $\{p\}\subseteq Z$ , we get $(\{p\},X){\models_{\small{LPST}}} {B(r)}$ for every $r\in{P}_5'$ , which leads to ${{{{\mathcal{T}}_{{P}_5',X}}^{\small{LPST}}}\uparrow \infty}= {{{{\mathcal{T}}_{{P}_5',X}}^{\small{LPST}}}\uparrow 2}= {{{{\mathcal{T}}_{{P}_5',X}}^{\small{LPST}}}(\{p\})}= \{x_1,x_2,x_3,p\}= X$ . This shows that X is an LPST-answer set of ${P}_5'$ .

The programs ${P}_5$ and ${P}_5'$ illustrate that the Check task for LPST-answer sets can be used to decide whether an instance of the NP-complete subset sum problem is (un)satisfiable, as programs following the same scheme along with an interpretation consisting of all atoms capture the complement of subset sum for arbitrary multisets of weights and bounds. Moreover, Section 2.2 discusses reductions of subset sum and the likewise NP-complete subset product problem to the satisfiability of aggregate expressions with avg or times, respectively, so that their complementary aggregate expressions with $\neq$ as comparison operator also make the Check task coNP-complete.

For a program P with arbitrary aggregate expressions and a given model X of P, the Check task of deciding whether X is an MR-answer set of P can be accomplished by guessing, for each aggregate expression $A\in\bigcup_{r\in{{P}^{X}}}{B(r)}$ , an interpretation $Z_A\subseteq X$ such that $Z_A\models A$ . Given that $X\models A$ , such an interpretation $Z_A$ exists for every A under consideration and can be used to witness that $(Y,X){\models_{\small{MR}}} A$ for interpretations $Z_A\subseteq Y\subseteq X$ . Checking whether $Z_A\subseteq Y$ instead of taking the condition of $(Y,X){\models_{\small{MR}}} A$ as such, in order to approximate ${{{{\mathcal{T}}_{{P},X}}^{\small{MR}}}(Y)}$ for some $Y\subseteq X$ , yields a tractable immediate consequence operator, whose least fixpoint matches ${{{{\mathcal{T}}_{{P},X}}^{\small{MR}}}\uparrow \infty}$ for well-chosen interpretations $Z_A$ . This shows that the Check task for MR-answer sets stays in NP also in the presence of non-convex aggregate expressions.

For establishing NP-hardness, the complexity of checking the existence of some $Z\subset{\small{AT}(A)}\cap X$ such that $Z\models A$ for an aggregate expression A with $X\models A$ matters, as the construction of ${{{{\mathcal{T}}_{{P},X}}^{\small{MR}}}\uparrow \infty}$ gets tractable and the complexity of Check drops to P when the satisfiability of aggregate expressions (by some smaller interpretation) can be determined in polynomial time. As the discussion in Section 2.2 shows, deciding satisfiability is NP-hard only for aggregate expressions with sum, times, or avg along with the comparison operator $=$ , so that any other (non-convex) aggregate expressions do not make the Check task NP-complete. However, for an aggregate expression A of the form $\small{TIMES}{[w_1:p_1, \dots, w_n:p_n]}={w_0}$ such that ${w_0}=0$ , only singletons $Z=\{p\}$ with ${\alpha(A,Z)}=0$ are relevant as subsets $Z\subset{\small{AT}(A)}\cap X$ such that $Z\models A$ . Otherwise, if $w_0\neq 0$ , we have to guarantee that ${\alpha(A,X\setminus Z)}=1$ , so that a linear collection of ( $\subseteq$ -minimal) subsets $Z\subset {\small{AT}(A)}\cap X$ with $Z\models A$ is obtained by excluding atoms $p\in X$ such that ${\alpha(A,\{p\})}=1$ together with a maximum even number of atoms $p\in X$ such that ${\alpha(A,\{p\})}=-1$ . As there are at most $|{\small{AT}(A)}\cap X|$ relevant $Z\subset {\small{AT}(A)}\cap X$ in either case, aggregate expressions with times do not yield NP-completeness of the Check task for MR-answer sets. The next example illustrates that this is different for aggregate expressions with sum or avg along with the comparison operator $=$ .

Example 13 Let us investigate the model $X=\{x_1,x_2,x_3,p\}$ of the following program ${P}_6$ :

\begin{alignat}{1} \tag{$r_{24}$} & x_1 \leftarrow \top \\ \tag{$r_{25}$} & x_2 \leftarrow \top \\ \tag{$r_{26}$} & x_3 \leftarrow \top \\ \tag{$r_{27}$} & p \leftarrow \small{SUM}{[2 : x_1, 2 : x_2, 3 : x_3, -2 : p]} = 5\end{alignat}

In order to decide whether X is an MR-answer set of ${P}_6$ , we need to construct ${{{{\mathcal{T}}_{{P}_6,X}}^{\small{MR}}}\uparrow \infty}$ , where ${{{{\mathcal{T}}_{{P}_6,X}}^{\small{MR}}}\uparrow 1}={{{{\mathcal{T}}_{{P}_6,X}}^{\small{MR}}}(\emptyset)}=\{x_1,x_2,x_3\}$ in view of the facts r ₂₄, r ₂₅, and r ₂₆. Then, the condition of $(\{x_1,x_2,x_3\},X){\models_{\small{MR}}} {B(r_{27})}$ is fulfilled if there is some interpretation $Z\subseteq \{x_1,x_2,x_3\}$ such that ${\alpha(\small{SUM}{[2 : x_1, 2 : x_2, 3 : x_3, -2 : p]} = 5,Z)} = 5$ . This is the case for $Z=\{x_1,x_3\}$ (and $Z=\{x_2,x_3\}$ ), so that

\begin{alignat*}{1} {{{{\mathcal{T}}_{{P}_6,X}}^{\small{MR}}}\uparrow \infty}={{{{\mathcal{T}}_{{P}_6,X}}^{\small{MR}}}\uparrow 2}={{{{\mathcal{T}}_{{P}_6,X}}^{\small{MR}}}(\{x_1,x_2,x_3\})}= \{x_1,x_2,x_3,p\}=X\text{.}\end{alignat*}

When we replace the rule r ₂₇ by

\begin{alignat}{1} \tag{$r_{27}'$} & p \leftarrow \small{SUM}{[2 : x_1, 2 : x_2, 3 : x_3, -1 : p]} = 6\end{alignat}

in the modified program ${P}_6'$ , there is no $Z\subseteq \{x_1,x_2,x_3\}$ such that ${\alpha(\small{SUM}{[2 : x_1, 2 : x_2, 3 : x_3, -1 : p]} = 6,Z)} = 6$ , so that ${{{{\mathcal{T}}_{{P}_6',X}}^{\small{MR}}}\uparrow \infty}={{{{\mathcal{T}}_{{P}_6',X}}^{\small{MR}}}\uparrow 1}=\{x_1,x_2,x_3\}$ disproves X to be an MR-answer set of ${P}_6'$ . Both programs ${P}_6$ and ${P}_6'$ are devised such that the construction of ${{{{\mathcal{T}}_{{P}_6,X}}^{\small{MR}}}\uparrow \infty}$ or ${{{{\mathcal{T}}_{{P}_6',X}}^{\small{MR}}}\uparrow \infty}$ , respectively, involves checking whether an instance of the subset sum problem is satisfiable. If so, the weight associated with the atom p to be concluded is set such that the desired bound is obtained by summing up all weights. As programs following the same scheme along with an interpretation consisting of all atoms can be used to decide arbitrary instances of subset sum, the Check task for MR-answer sets is NP-complete in the presence of non-convex aggregate expressions of the form $\small{SUM}{[w_1:p_1, \dots, w_n:p_n]}={w_0}$ .

Rules like r ₂₇ and r _27’ can also be adjusted to use the aggregation function avg instead of sum by introducing an additional fact $x\leftarrow \top$ and taking the inverse of the original bound as weight for x:

\begin{alignat}{1} \tag{$r_{28}$} & p \leftarrow \small{AVG}{[2 : x_1, 2 : x_2, 3 : x_3, -5 : x, -2 : p]} = 0 \\ \tag{$r_{28}'$} & p \leftarrow \small{AVG}{[2 : x_1, 2 : x_2, 3 : x_3, -6 : x, -1 : p]} = 0\end{alignat}

The condition of $(\{x_1,x_2,x_3,x\},X\cup\{x\}){\models_{\small{MR}}} {B(r_{28})}$ or $(\{x_1,x_2,x_3,x\},X\cup\{x\}){\models_{\small{MR}}} {B(r_{28}')},$ respectively, then again amounts to deciding the satisfiability of an underlying instance of subset sum. Hence, we have that the Check task for MR-answer sets is likewise NP-complete for programs including non-convex aggregate expressions of the form $\small{AVG}{[w_1:p_1, \dots, w_n:p_n]}={w_0}$ .

4.2 Answer set existence

The Exist reasoning task addresses the decision problem of whether a program P has some ${\Delta}$ -answer set for ${\Delta}\in\{\small{FFLP}, \small{GZ}, \small{LPST}, \small{MR}, \small{DPB}\}$ , that is, a decision problem similar to Check but having no fixed interpretation $X\subseteq \mathcal{P}$ . The summary of completeness properties for particular complexity classes is provided in Table 2, where completeness now also applies for P in view of the well-known P-completeness of deciding whether the $\subseteq$ -minimal model of a positive program includes some atom of interest (Dantsin et al. Reference Dantsin, Eiter, Gottlob and Voronkov2001). In fact, when using (monotone) aggregate expressions of the form $\small{SUM}{[1:p]}>0$ to represent propositional atoms p in the bodies of rules, all ${\Delta}$ -answer set semantics reproduce the $\subseteq$ -minimal model of a positive program as the unique ${\Delta}$ -answer set. Given that our notion of non-disjunctive programs syntactically allows for constraints, a program does not necessarily have a ( $\subseteq$ -minimal) model though, even when all aggregate expressions are monotone, which makes the Exist task non-trivial and thus P-complete. While going beyond the simple form $\small{SUM}{[1:p]}>0$ of monotone aggregate expressions lets the GZ-answer set semantics diverge from the other aggregate semantics, as observed on Example 11, such additional syntactic freedom does not increase the computational complexity any further because the ${\Delta}$ -answer set semantics, for ${\Delta}\in\{\small{FFLP}, \small{LPST}, \small{MR}, \small{DPB}\}$ , still coincide and the constructions by means of different immediate consequence operators remain tractable.

Regarding anti-monotone and convex aggregate expressions, the rows for the Exist task in Table 2 follow the pattern of Check, where P-membership or coNP-completeness, respectively, of Check leads to NP- or $\Sigma_2^{\small{P}}$ -completeness of Exist. For NP-hardness, anti-monotone aggregate expressions of the form $\small{SUM}{[1:p]}<1$ are sufficient, as they allow for representing negated propositional atoms p in rule bodies, which directly lead to elevated complexity of deciding whether some (standard) answer set exists (Marek and TruszczyŃski Reference Marek and TruszczyŃski1991). Likewise, the $\Sigma_2^{\small{P}}$ -hardness of Exist for DPB-answer sets follows from the simultaneous availability of monotone and anti-monotone aggregate expressions of the form $\small{SUM}{[1:p]}>0$ or $\small{SUM}{[1:p]}<1$ , as the reduction from quantified Boolean formulas (with one quantifier alternation) by Denecker et al. (Reference Denecker, Marek and TruszczyŃski2004) shows.

The additional availability of non-convex aggregate expressions in programs with arbitrary aggregate expressions does not increase the complexity of Exist beyond NP for GZ- as well as MR-answer sets. Regarding GZ-answer sets, the strong condition ${\small{AT}(A)}\cap Y = {\small{AT}(A)}\cap X$ for $(Y,X){\models_{\small{GZ}}} A$ is unaffected by the monotonicity of an aggregate expression A (Alviano and Leone Reference Alviano and Leone2015), as already observed on the tractability of the Check task. The latter reasoning task happens to be in NP for MR-answer sets, so that deciding whether a program including non-convex aggregate expressions has some MR-answer set does not involve orthogonal combinatorial problems. Unlike that, the $\Sigma_2^{\small{P}}$ -hardness of Exist for DPB-answer sets is established already for programs with convex aggregate expressions, and non-convex aggregate expressions do not make a difference here because neither determining candidate models X of a program P nor checking whether ${{{{\mathcal{T}}_{{P},X}}^{\small{DPB}}}\uparrow \infty}=X$ becomes more complex in their presence.

The complexity of Exist for FFLP-answer sets correlates to the monotonicity of aggregate expressions, given the same consideration as for Check that (proper) disjunctive rules can be captured in terms of non-disjunctive programs including non-convex aggregate expressions (Ferraris Reference Ferraris2011). This yields $\Sigma_2^{\small{P}}$ -completeness of the Exist task for FFLP-answer sets of programs with non-convex aggregate expressions regardless of their particular aggregation functions, comparison operators, weights and bounds (Alviano and Faber Reference Alviano, Faber, Cabalar and Son2013). While the complexity of Exist is in general the same for LPST-answer sets, the $\Sigma_2^{\small{P}}$ -hardness again depends on the complexity of deciding the satisfiability of the complement of a (non-convex) aggregate expression A. That is, the complexity drops to NP without aggregate expressions $\small{AGG}{[w_1:p_1, \dots, w_n:p_n]}\neq{w_0}$ such that $\small{AGG}\in\{\small{SUM}, \small{TIMES}, \small{AVG}\}$ because the underlying Check task for LPST-answer sets gets tractable when programs do not involve aggregate expressions of this form. As further detailed in the next example, aggregate expressions with sum or avg along with the comparison operator $\neq$ allow for expressing the $\Sigma_2^{\small{P}}$ -complete generalized subset sum problem (Berman et al. Reference Berman, Karpinski, Larmore, Plandowski and Rytter2002), so that the same complexity is obtained for LPST-answer sets of programs including such non-convex aggregate expressions. Although we are unaware of literature addressing the complexity of a corresponding generalized version of the subset product problem, the coNP-hardness of the Check task suggests that Exist remains $\Sigma_2^{\small{P}}$ -hard with times as well.

Example 14 As checked in Examples 6 and 10, the interpretation $X=\{y_1,x_2,z_1,z_2,p\}$ is the unique ${\Delta}$ -answer set, for ${\Delta}\in\{\small{FFLP},\small{LPST},\small{DPB}\}$ , of the program ${P}_3$ :

\begin{alignat}{1} \tag{$r_6$} & x_1 \leftarrow \small{SUM}{[1:y_1]} < 1 \\ \tag{$r_7$} & y_1 \leftarrow \small{SUM}{[1:x_1]} < 1 \\ \tag{$r_8$} & x_2 \leftarrow \small{SUM}{[1:y_2]} < 1 \\ \tag{$r_9$} & y_2 \leftarrow \small{SUM}{[1:x_2]} < 1 \\ \tag{$r_{10}$} & z_1 \leftarrow \small{SUM}{[1:p]} > 0 \\ \tag{$r_{11}$} & z_2 \leftarrow \small{SUM}{[1:p]} > 0 \\ \tag{$r_{12}$} & p \leftarrow \small{SUM}{[1:y_1,2:y_2,2:z_1,3:z_2]} \neq 5 \\ \tag{$r_{13}$} & \bot \leftarrow \small{SUM}{[1:p]} < 1.\end{alignat}

In fact, $\{y_1,y_2\}\cap X=\{y_1\}$ represents the single solution to the instance

\begin{alignat*}{1} \exists y_1 y_2 \forall z_1 z_2 (1\cdot y_1+ 2\cdot y_2+ 2\cdot z_1+ 3\cdot z_2 \neq 5)\end{alignat*}

of the generalized subset sum problem. The rules $r_6$ , $r_7$ , $r_8$ , and $r_9$ make use of the auxiliary atoms $x_1$ and $x_2$ to express exclusive choices between $x_1$ and $y_1$ as well as $x_2$ and $y_2$ , where the chosen atoms $y_i$ stand for a solution candidate. If the candidate is indeed a solution, any truth assignment of the atoms $z_i$ leads to a weighted sum that is different from the bound, which is 5 for our instance. In this case, we have that $Z\models {B(r_{12})}$ for every interpretation $\{y_1,y_2\}\cap X\subseteq Z \subseteq X$ , so that the head atom p must necessarily be true and is also concluded by the operators ${{{\mathcal{T}}_{{P}_3,X}}^{\small{LPST}}}$ as well as ${{{\mathcal{T}}_{{P}_3,X}}^{\small{DPB}}}$ . The remaining rules $r_{10}$ and $r_{11}$ establish that the atoms $z_i$ follow from p, which makes sure that a potential counterexample, that is, some truth assignment of the atoms $z_i$ such that the weighted sum matches the given bound, corresponds to a smaller interpretation $Y\subset X$ disproving X to be a ${\Delta}$ -answer set of ${P}_3$ . Finally, the constraint $r_{13}$ expresses that p must be true, while its provability relies on $r_{12}$ , and thus eliminates any solution candidate that would directly give the bound as weighted sum when all of the atoms $z_i$ are assigned to false.

Introducing an additional fact $x\leftarrow \top$ and replacing $r_{12}$ by

\begin{alignat}{1} \tag{$r_{12}'$} & p \leftarrow \small{AVG}{[1:y_1,2:y_2,2:z_1,3:z_2,-5:x]} \neq 0\end{alignat}

leads to a modified program ${P}_3'$ including a non-convex aggregate expression with avg instead of sum. This aggregate expression takes the inverse of the original bound as weight for a necessarily true atom x, so that the average happens to be 0 if and only if the weighted sum over the remaining (true) atoms matches the bound. Hence, we have that ${\Delta}$ -answer sets $X\cup\{x\}$ of ${P}_3'$ correspond to ${\Delta}$ -answer sets X of ${P}_3$ for ${\Delta}\in\{\small{FFLP},\small{LPST},\small{DPB}\}$ .

Given that programs following the scheme of ${P}_3$ or ${P}_3'$ , respectively, allow for expressing arbitrary instances of generalized subset sum, we conclude that the Exist task for the three aggregate semantics of interest, in particular, LPST-answer sets of programs with non-convex aggregate expressions as used in ${P}_3$ and ${P}_3'$ , is $\Sigma_2^{\small{P}}$ -hard. Such elevated complexity is not obtained for GZ- and MR-answer sets, and as discussed in Example 10, the program ${P}_3$ does not have any GZ-answer set although the corresponding instance of generalized subset sum is satisfiable, while X and two more interpretations that do not represent solutions are MR-answer sets of ${P}_3$ .

Finally, note that the computational complexity of the Check and Exist reasoning tasks is a common subject of investigation for specific logic programs. In this regard, the comparably low complexity for GZ-answer sets does not come as a surprise, as avoiding so-called vicious circles (Gelfond and Zhang Reference Gelfond and Zhang2019) circumvents elevated complexity due to (sophisticated) aggregate expressions. Hardness properties concerning DPB-answer sets are immediate consequences of the simultaneous availability of monotone and anti-monotone aggregate expressions, given the computational complexity of the so-called ultimate semantics (Denecker et al. Reference Denecker, Marek and TruszczyŃski2004), and the complexity of reasoning tasks for FFLP-answer sets has been thoroughly studied in the corresponding literature (Alviano and Faber Reference Alviano, Faber, Cabalar and Son2013; Faber et al. Reference Faber, Pfeifer and Leone2011; Ferraris Reference Ferraris2011). For LPST-answer sets, the elevated complexity due to aggregate expressions of the form $\small{SUM}{[w_1:p_1, \dots, w_n:p_n]}\neq{w_0}$ or $\small{AVG}{[w_1:p_1, \dots, w_n:p_n]}\neq{w_0}$ has been put forward by Son and Pontelli (Reference Son and Pontelli2007), and we here add $\small{TIMES}{[w_1:p_1, \dots, w_n:p_n]}\neq{w_0}$ to these considerations. To our knowledge, the computational complexity of reasoning tasks for MR-answer sets has not been investigated in depth, and the NP-hardness of Check for programs with aggregate expressions $\small{SUM}{[w_1:p_1, \dots, w_n:p_n]}={w_0}$ or $\small{AVG}{[w_1:p_1, \dots, w_n:p_n]}={w_0}$ was unrecognized before.