Managing controversial information is a challenging issue in AI. Formal argumentation is an important area of AI concerned with reasoning about supporting and opposing arguments involved in decision-making processes. In abstract argumentation frameworks, each argument can be associated with an acceptance condition, which can be either implicit (e.g. in Dung's framework) or explicit (e.g. in the Dialectical Framework, where propositional formulas are associated with arguments/statements). However, existing argumentation frameworks that allow explicit conditions may not always offer a concise and intuitive way to express general acceptance conditions, such as those that can be expressed using first-order logic formulas. In this paper, we discuss the recently introduced Abstract Reasoning Framework (ARF) [1], that is an argumentation framework where arguments' acceptance conditions allow for checking general properties also concerning sets of arguments/statements by exploiting aggregate functions.
Argumentation is used in our daily life to explain our reasons for or against claims in our
discussions, persuade other people, and derive conclusions in a step-wise fashion. Most of
the situations where argumentation takes place are inherently characterized by the presence of
controversial information. Enabling automated systems to process such kind of information,
much in the same way as organized human discussions are carried out, is an important challenge
that have deserved increasing attention from the Artificial Intelligence community in the last
decades. This has led to the development of an important and active research area called formal
argumentation [
Despite the expressive power and generality of AFs, in some cases it is difficult to accurately
model domain knowledge by an AF in a natural and easy-to-understand way. For this reason,
Dung’s framework has been extended by introducing further constructs, such as preferences
[
As an example, consider now the case where there are people attending a party and that some pairs of people (e.g. male-female couples) attending together the party have the same ticket. Now person d says that they will attend the party if there are at least pairs of people with the same ticket. To express such a condition in existing frameworks such as GRAPPA [28], several additional (meta-)statements have to be introduced to represent groups of 2 people sharing the same ticket among people, thus possibly introducing (︀ )︀ new statements; in general, we 2 would have (︀ )︀ new statements if groups of people sharing the same ticket are considered. Moreover, considering the ADF framework [29] (a generalization of AF that allows explicit acceptance conditions over arguments using propositional formulae), it is not possible to naturally express acceptance conditions taking into account general properties on groups of objects that, for instance, can be easily expressed by using first-order logics. On the other side, the GRAPPA framework, that has firstly addressed the problem and proposed a solution, in some cases is not sufficiently flexible to easily express situations such as that mentioned above, as it could require the introduction of several additional statements, sometimes exponential.
Thus, in this paper we present the novel framework called Abstract Reasoning Framework
(ARF) [
We briefly summarize the basic concepts underlying the notion of partial stable models of logic programs [30], as ARF semantics relies on that.
A (normal, logic) program is a set of rules of the form ← 1 ∧ · · · ∧ , with ≥ 0, where is an atom, called head and denoted by ℎ(), and 1 ∧ · · · ∧ is a conjunction of literals, called body and denoted by (). With a little abuse of notation, () also denotes the set of literals in the body of . We consider programs without function symbols.
Given a program , ( ) denotes the set of all ground instances of the rules in . The Herbrand Base of a program , i.e. the set of all ground atoms which can be constructed by using predicate and constant symbols occurring in , is denoted by , whereas ¬ denotes the set {¬ | ∈ }. Analogously, for any set ⊆ ∪ ¬ , ¬ denotes the set {¬ | ∈ }, where ¬¬ = . Given ⊆ ∪ ¬ , ( ) (resp., ( ), ( )) stands for ∩ (resp., ¬ ∩ , ∖ (( ) ∪ ( ))). is consistent if ( ) ∩ ¬( ) = ∅, otherwise is inconsistent. A set ⊆ ∪ ¬ is a (partial) interpretation of if is consistent; is total if ( ) ∪ ( ) = . For any partial interpretation of a program , the atoms in ( ) (resp., in ( ), ( )) are said to be true (resp., false, undefined ) w.r.t. . The truth value, either t (true), f (false) or u (undefined), of an atom w.r.t. an interpretation is denoted by (). We assume the truth values ordering f < u < t and that ¬u = u.
A partial interpretation of a program is a partial model of if for each rule ∈ ( ), (ℎ()) ≥ (()). Given a program and a partial interpretation , the reduct of w.r.t. , denoted by , is obtained from ( ) by replacing each negated literal with its truth value in . Clearly, rules having in the body the truth value f can be deleted, and the truth value t can be deleted from the body of rules.
As is a positive program, the minimal Herbrand model of can be obtained as the least ifxpoint of its immediate consequence operator , denoted by (∅), containing true and undefined atoms. Let Ψ be the set of atoms which are either true or false w.r.t. (∅) (false atoms are those in that do not occur in (∅) neither as true atoms nor as undefined atoms), then Ψ is minimal w.r.t. (Ψ ) and maximal w.r.t. (Ψ ).
Let be a program and a partial model of . Then is a Partial Stable Model (PSM) of iff = Ψ . The set of partial stable models of a logic program define a meet semi-lattice. The well-founded model and the maximal-stable models are defined by considering the ⊆ minimal and ⊆ -maximal elements. The set of (total) stable models is obtained by considering the maximal-stable models which are total, whereas the least-undefined (a.k.a. semi-stable) models are obtained by considering the maximal-stable models with a ⊆ -minimal set of undefined atoms.
The set of partial stable (resp., maximal-stable, (total) stable, least-undefined, well-founded) models of will be denoted by ( ) (resp., ℳ( ), ( ), ℒ( ), ( )). Example 2. Consider the program = {a ← ¬ b; b ← ¬ a; c ← ¬ a ∧ ¬b ∧ ¬d; d ← ¬ c}. The set of PSMs of is ( ) = {∅, {¬c, d}, {a, ¬b, ¬c, d}, {¬a, b, ¬c, d}}. Then, ( ) = {∅}, whereas ( ) = ℳ( ) = ℒ( ) = {{a, ¬b, ¬c, d}, {¬a, b, ¬c, d}}. □
We now present the syntax and the semantics of Abstract Reasoning Framework [
The language used to define acceptance conditions considers numerical terms, that is, natural numbers or terms built by using natural numbers, aggregate functions over set terms (defined using general properties on groups of objects), and standard arithmetic functions. Moreover, in addition to user-defined atoms, built-in atoms constructed by using numerical terms and comparison predicates are also allowed. Specifically, the alphabet consists of the following sets: • Constants , consisting of a set of user-defined objects (denoted by names starting with a lowercase letter) and the set N of natural numbers; • Variables , denoted by names starting with an uppercase letter; • Functions ℱ , consisting of arithmetic functions1 +, − , × and aggregate functions , , and ; • Predicates Π , consisting of a set of user-defined predicates and the built-in predicates >, ≥ , <, ≤ , =, ̸= (also called comparison operators); • Logical connectives ℒ = {∧, ¬}.
As illustrated below, we assume the existence of set terms that can be defined by specifying their properties (by a logical formula to be satisfied). Aggregate functions , , and are assumed to be applied to the first element of the tuples in the input set. Thus, in constructing formulae defining generalized acceptance conditions, we use atoms having as terms both simple terms and aggregate terms, that is aggregate functions applied to set terms.
The basic elements for building acceptance conditions are: • Simple terms, that are constants and variables; • User-defined atoms , built by using predicates in and simple terms as usual. • Built-in atoms of the form 1 ⊙ 2, where 1 and 2 are arithmetic expressions built by using natural numbers and aggregate terms (see next) and ⊙ is a comparison operator. • Literals, consisting of built-in atoms or possibly negated user-defined atoms. Analogously to atoms, literals are distinguished between user-defined and built-in ones. • Set terms of the form { | ( , )}, where ( , ) is a safe conjunction of literals2 such that built-in atoms contain only simple terms; here is a list of so-called aggregate variables, whereas is the list of remaining variables, called existential variables. • Aggregate terms of the form ( ), where = { | ( , )} is a set term and is an aggregate function. • Logical rules having in the head a ground user-denfied atom and in the body a conjunction of ground user-defined literals and built-in literals.
Notice that the above definitions do not allow to have nested aggregate terms (i.e. only simple
terms can occur inside aggregate terms). W.l.o.g., we can assume that rules may have at most
one built-in atom with aggregate terms. It is also assumed that: i) conjunctions inside set terms
are safe [31], ii) variables occurring in an aggregate term do not occur elsewhere outside the
aggregate term in the same rule, and iii) built-in atoms are monotonic. Intuitively, a built-in atom
is monotonic if by enlarging the set terms occurring in it, its truth value does not decrease (e.g. if
it was t it cannot become f after enlarging the set). These properties are discussed in detail in [
We are now ready to introduce the ARF syntax.
1The operator / has been excluded to avoid possible division by zero.
2Intuitively, safeness prescribes that variables take values from a finite domain.
Definition 1 (ARF Syntax). An Abstract Reasoning Framework (ARF) is a tuple ⟨, , , ⟩, where is a finite set of objects, is a set of predicates, is a finite set of statements built by using predicates in and constants in , and is a finite set of logical rules defining all statements in .
Example 3. Continuing with Example 1, assume now that Carol changes her mind and says that she will join the party if Bob does not. For the new party planning scenario, we obtain the following ARF ∆ 3 = ⟨{a, b, c, d}, {j}, {j(a), j(b), j(c), j(d)}, 3⟩, where a, b, c, d respectively denote Antony, Bob, Carol, David, the 1-arity predicate j stands for joins the party, and 3 is as follows: j(a) ← ¬ j(c) ← ¬ j(b) j(b) j(b) ← ¬ j(d) ←
j(a) count{X | j(X) ∧ X ̸= d} ≥ 2.
In the last rule, j(X) is a user-defined atom, whereas X ̸= d is a built-in atom containing only simple terms. On the other side, count{X | j(X) ∧ X ̸= d} ≥ 2 is a (monotonic) built-in atom containing an aggregate term. Notably, for the more general situation described in the introduction, where d joins the party only if at least people will do, in the rule defining j(d) we simply need to replace 2 with . □
Considering the tight connection between ARF and logic programming, we propose a semantics based on an extension of that proposed in [32] for logic programs with aggregates under total stable model semantics. The semantics of an ARF ∆ = ⟨, , , ⟩, given by the partial stable models of , is obtained in two steps: () first, a dual set of rules ◇ derived from by rewriting rules with aggregates is generated, and then () for a given candidate partial stable model , the P-reduct ◇ (a ground, positive, standard program where aggregates are replaced by conjunctions of atoms) is generated and it is checked that is the fixpoint of the immediate consequence operator ◇ .
For any ARF ∆ =
⟨, , , ⟩, the dual set of rules ◇ is derived from by: 1. replacing every aggregate term {| (, )} with a fresh variable (called auxiliary variable), and adding to the body of the rule where it appears an auxiliary atom ( ) (where is a fresh predicate); 2. adding for each auxiliary atom ( ), used to replace an aggregate term { | (, )}, the following two aggregate rules: ′ : ( ) ← ′′ : ( ) ← = { | (, ) ≡ t}, = { | (, ) ̸≡ f }, where the body atom = {· · · }
is called aggregate atom.
Thus, rules’ bodies of ◇ consist of either a conjunction of literals not containing aggregate terms or a single aggregate atom. Intuitively, in the dual set ◇ , heads of rules containing an aggregate atom can be derived from instances of set terms whose truth value is true or undefined . For the logical connective ≡ there are different 3-valued semantics; we refer here to the Lukasiewicz’s logic stating that the truth value of ≡ is true if the truth values of and coincide, false if one is false and the other one is true, undefined otherwise.
The difference between and ◇ is that in ◇ we have introduced new auxiliary atoms to compute intermediate values related to aggregate terms.
Example 4. Considering the set of rules 3 of ∆ 3, the dual set of rules ◇3 is as follows: j(a) ← ¬ j(b) ← ¬ j(c) ← ¬ j(d) ← j(b) j(a) j(b) j′(V) ∧ V ≥ 2 j′(V) ← j′(V) ←
V = count{X | (j(X) ∧ X ̸= d) ≡ t} V = count{X | (j(X) ∧ X ̸= d) ̸≡ f } where a, b, c, d are constants, V is an auxiliary variable and j′(V) is an auxiliary atom. □
We now define the satisfiability of literals and aggregate atoms. To this end, for any ARF ∆ = ⟨, , , ⟩, we denote by (◇ ) the program derived from ◇ by replacing auxiliary variables with constants in N in all possible ways. Let be the set of atoms occurring in the heads of rules in (◇ ). A partial interpretation for ◇ is a consistent subset of ∪ ¬ , that is, for each auxiliary predicate , defines at most one atom () as true (contained in the interpretation) and at most one atom (′) as undefined.
For instance, considering Example 4, the partial interpretation = {j(a), ¬j(b), j′(1)} ∪ {¬j′(x) | x ∈ (N ∖ {1})} is consistent, while ′ = {j(a), ¬j(b), j′(1), j′(2)} ∪ {¬j′(x) | x ∈ (N ∖ {1, 2, 3, 4})} is not. Observe that interpretations for are finite whereas interpretations for ◇ can be infinite, though enumerable and finitely representable.
A partial interpretation for an ARF ⟨, , , ⟩ is a consistent set such that ⊆ ∪ ¬. Definition 2 (Satisfiability of literals and aggregate atoms). and let be a partial interpretation for ◇ . Then: Let ∆ = ⟨, , , ⟩ be an ARF • a user-defined, ground literal ℓ is true (resp., false, undefined) w.r.t. if ℓ ∈ (resp., ¬ℓ ∈ , neither ℓ ∈ nor ¬ℓ ∈ ); • the truth value of a ground built-in literal is computed in the standard way and it is either true or false; • an aggregate atom = { | (, )}, with ∈ N, is: – true w.r.t. if, let be the value of { | (, ) ≡ t} computed over , the arithmetic statement = is true; for ∈ {, } it is also required that |{ | (, ) ≡ t}| > 0; – undefined w.r.t. if, let be the value of { | (, ) ̸≡ f } computed over , the arithmetic statement = is false and the arithmetic statement = is true; for ∈ {, } it is also required that |{ | (, ) ̸≡ f }| > 0; – false w.r.t. , otherwise.
Observe that if is a total interpretation then literals and aggregate atoms are either true or false w.r.t. . Indeed, any aggregate atom cannot be undefined because (, ) ≡ t is equivalent to (, ) ̸≡ f .
ARF’s partial stable model semantics extends the total stable model semantics for normal programs with aggregates defined in [ 32] and is based on the novel concept of P-reduct of the dual program, defined as follows.
Definition 3 (P-Reduct). Given an ARF ∆ = ⟨, , , ⟩ and a partial interpretation for ◇ , the P-reduct ◇ is obtained from (◇ ) by: 1. deleting: a) aggregate rules whose body atom = ( ) is false w.r.t. , b) rules having in the body an auxiliary atom not defined by any rule (i.e. there are no rules having that atom in the head), and 2. replacing: a) every aggregate atom = { | (, ) ≡ t} that is true w.r.t. with the conjunction ⋀︀{ (, ) | (, ) is true w.r.t. }; b) every aggregate atom = { | (, ) ̸≡ f } that is not false w.r.t. with the conjunction ⋀︀{ (, ) | (, ) is not false w.r.t. }; c) every negative (user-defined) body literal and built-in literal with its truth value w.r.t. ; where and are lists of constants replacing the list of variables and , respectively.
Therefore, ◇ is derived from (◇ ) and , after deleting useless rules (items 1.a and 1.b), by performing the same steps as done for standard programs (item 2.c), and by replacing aggregate rules with standard rules (items 2.a and 2.b). Clearly, rules in ◇ having in the body a truth value f may be omitted as they do not contribute to the computation of the minimum model. Therefore, for each auxiliary predicate , there are at most two rules defining it in ◇ .
It is worth noting that conjunctions (1, 1) ∧ · · · ∧ (, ) replacing aggregate atoms of the form = { | (, )} contain exactly elements (, ). Note also that if is a total interpretation for ◇ , then items 2.a and 2.b of Definition 3 are equivalent. We are now ready to define models for an ARF.
Definition 4 (ARF Semantics). An interpretation for an ARF ∆ = ⟨, , , ⟩ is a partial stable model (PSM) for ∆ if there exists an interpretation for ◇ such that: i) is the minimal model of the P-reduct ◇ , and ii) = ∩ ( ∪ ¬).
Notice that for ARFs where is a standard program (not containing aggregate terms), the definition of partial stable model coincides with that of logic programs, as ◇ coincides with and an interpretation for it has no auxiliary atoms.
Example 5. Considering the set of rules 3 of ∆ 3 (see Example 3), the dual set of rules ◇3 (see Example 4), and the the interpretation 1 = {j(a), ¬j(b), j(c), j(d), j′(2)} ∪ {¬j′(x) | x ∈ (N ∖ {2})} for ◇3, the P-reduct ◇31 is: j(a) ← j(d) ←
We use (∆) to denote the set of PSMs for ∆ . Consistently with the terminology of Section 2, a maximal-stable model is a ⊆ -maximal PSM for ∆ . A (total) stable model is a maximal-stable model for ∆ that is total, and a least-undefined model is a maximal-stable model for ∆ with a ⊆ -minimal set of undefined statements.
Example 6. ARF ∆ 3 has 3 PSMs: 0 = ∅, 1 = {j(a), ¬j(b) j(c), j(d)} and 2 = {¬j(a), j(b), ¬j(c), ¬j(d)}. 1 and 2 are maximal-stable, stable, and least-undefined. However, it is not always true that the maximal-stable models are also (total) stable. Indeed, consider the ARF ∆ 6 obtained from ∆ 3 by replacing the rule j(c) ← ¬ j(b) with j(c) ← ¬j(b) ∧ ¬j(c). In this case we have that ∆ 6 has 3 PSMs: 0 = ∅, 1 = {j(a), ¬j(b)} and 2 = {¬j(a), j(b), ¬j(c), ¬j(d)}. 1 is maximal-stable, but not (total) stable, while 2 (total) stable and, therefore, also maximal-stable and least-undefined. □
We have discussed the Abstract Reasoning Framework (ARF), that is a simple yet expressive
argumentation framework where arguments’ acceptance conditions allow aggregates and whose
semantics is built on basis of the proposal of [32] that naturally extends (total) stable model
semantics for standard logic programs to logic programs with aggregates. Aggregates over
set terms have been studied in different contexts such as databases, logic programming, and
argumentation-based frameworks. Interestingly, it can be shown that ARF generalizes several
existing AF-based frameworks (e.g. Bipolar AF [33], AFRA, ASAF, and Recursive AF [
Acknowledgments. We acknowledge financial support from PNRR MUR project PE0000013FAIR and Next Generation EU project ECS0000009 - Tech4You.
Properties and complexity, in: Proc. of AAAI, 2022, pp. 5451–5460. [22] G. Alfano, M. Calautti, S. Greco, F. Parisi, I. Trubitsyna, Explainable acceptance in probabilistic and incomplete abstract argumentation frameworks, Artif. Intell. 323 (2023) 103967. [23] H. Li, N. Oren, T. J. Norman, Probabilistic argumentation frameworks, in: Proc. of TAFA, 2011, pp. 1–16. [24] A. Hunter, Some foundations for probabilistic abstract argumentation, in: Proc. of COMMA, 2012, pp. 117–128. [25] B. Fazzinga, S. Flesca, F. Parisi, On the complexity of probabilistic abstract argumentation frameworks, TOCL 16 (2015) 22:1–22:39. [26] B. Fazzinga, S. Flesca, F. Parisi, On efficiently estimating the probability of extensions in abstract argumentation frameworks, Int. J. Approx. Reason. 69 (2016) 106–132. [27] G. Alfano, M. Calautti, S. Greco, F. Parisi, I. Trubitsyna, Explainable acceptance in probabilistic abstract argumentation: Complexity and approximation, in: Proc. of KR, 2020, pp. 33–43. [28] G. Brewka, S. Woltran, GRAPPA: A semantical framework for graph-based argument processing, in: Proc. of ECAI, 2014, pp. 153–158. [29] G. Brewka, H. Strass, S. Ellmauthaler, J. P. Wallner, S. Woltran, Abstract dialectical frameworks revisited, in: Proc. of IJCAI, 2013, pp. 803–809. [30] D. Saccà, The expressive powers of stable models for bound and unbound DATALOG queries, Journal of Computer and System Sciences 54 (1997) 441–464. [31] S. Abiteboul, R. Hull, V. Vianu, Foundations of Databases, Addison-Wesley, 1995. [32] M. Gelfond, Y. Zhang, Vicious circle principle, aggregates, and formation of sets in ASP based languages, Artificial Intelligence 275 (2019) 28–77. [33] F. Nouioua, AFs with necessities: Further semantics and labelling characterization, in: Proc.
of SUM, 2013, pp. 120–133. [34] G. Alfano, S. Greco, F. Parisi, A meta-argumentation approach for the efficient computation of stable and preferred extensions in dynamic bipolar argumentation frameworks, Intelligenza Artificiale 12 (2018) 193–211. [35] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, On the semantics of abstract argumentation frameworks: A logic programming approach, Theory and Practice of Logic Programming 20 (2020) 703–718. [36] M. Gebser, R. Kaminski, B. Kaufmann, T. Schaub, Multi-shot ASP solving with clingo,
Theory and Practice of Logic Programming 19 (2019) 27–82. [37] W. T. Adrian, M. Alviano, F. Calimeri, B. Cuteri, C. Dodaro, W. Faber, D. Fuscà, N. Leone, M. Manna, S. Perri, F. Ricca, P. Veltri, J. Zangari, The ASP system DLV: advancements and applications, Künstliche Intelligenz 32 (2018) 177–179.