Inference Operators for Argumentation Formalisms - The Case of Dung-style Frameworks

Abstract

We study abstract properties of possible inference operators for Dung-style Argumentation Frameworks. In this ifrst attempt, we revisit classical non-monotonic formalisms such as Default Logic and Logic Programming and adapt their core concepts to the realm of Dung's Argumentation Theory. The resulting operators provide initial formal insights and open avenues for future work, such as exploring the full range of existing semantics, acceptance modes or extending the approach to more expressive abstract and structured argumentation formalisms.

Keywords

• eol>Inference Operators
• Non-monotonic Reasoning
• Dung-style Argumentation Frameworks

1. Introduction

2. Inference Operators – Properties and Examples

In classical logic, a formula is said to be a logical consequence of a set of formulas, denoted |= , if and only if Mod( ) ⊆ Mod(). The classical consequence operator [ 6, 7 ] then yields the set of all such consequences, i.e.: Cn( ) = { | |= }. This operator can be generalized by allowing other kinds of inputs – for instance, diferent sets of well-formed formulas, atoms only, assumptions, or even arguments (formalized in an appropriate way). Let ℱ denote the set of suitable inputs, and let C be a function, a so-called inference operator, operating on subsets of ℱ , formally defined as: C : 2ℱ → 2ℱ , ↦→ C( ).

Consider the following abstract properties that enable a systematic comparison [ 8, 9 ]. Inclusion: ⊆ C( ) (no information from is lost), Idempotence: C(C( )) ⊆ C( ) (applying C again yields nothing new), Monotonicity: If ⊆ , then C() ⊆ C( ) (adding information preserves old conclusions),

Cautious Monotony: If ⊆ ⊆ C(), then C() ⊆ C( ) (new information already entailed doesn’t invalidate old results), Cut: If ⊆ ⊆ C(), then C( ) ⊆ C() (new information already entailed doesn’t give rise for new results), Cumulativity: If ⊆ ⊆ C(), then C( ) = C() (robustness under intermediate results), Compactness: C( ) ⊆ ⋃︀{C( ′) | ′ ⊆ , ′ finite } (finite subtheories sufice for inference), Supraclassicality: Cn( ) ⊆ C( ) (all classical consequences are preserved). Default Logic introduced by Raymond Reiter [ 10 ], is a nonmonotonic formalism based on defaults : :1,..., where is the prerequisite, 1, . . . , are consistency conditions, and is the conclusion.

For instance, the default 1 : kid():likesIceCream() expresses the knowledge “Kids usually like ice cream.” likesIceCream()

A default theory is a pair (, ), where is a set of defaults and a set of formulas, e.g., = {kid(ℎ)}. A Reiter extension is defined quasi-inductively as = ⋃︀∞ =0 with 0 = , and +1 = Cn() ∪ {︁ | :1,..., ∈ , ∈ , ¬ ∈/ for all }︁. Extensions need not always exist; there may be none, exactly one, or arbitrarily many. In our example, we obtain the unique extension = Cn({kid(ℎ), likesIceCream(ℎ)}).

The subsequent associated (sceptical) inference operator satisfies inclusion, idempotence, cut, and supraclassicality, but generally fails compactness, monotonicity, cumulativity, and cautious monotonicity. Definition 2.1 ( Inference operator – Reiter Extensions). Let ℰ(, ) denote the set of all extensions of a default theory (, ). The inference operator is defined as: C : 2ℱ → 2ℱ , ↦→ C( ) = ⋂︀ ℰ(, ) Logic Programs (LPs) are finite sets of rules of the form: : ← 1, . . . , , not 1, . . . , not where is the head of , and 1, . . . , (positive atoms) together with not 1, . . . , not (defaultnegated atoms) form the body of . For example, the rule 1 : Hunts() ← Owl (), not InZoo() states intuitively that “Owls hunt, unless they live in the zoo.” The famous stable model semantics introduced by Michael Gelfond and Vladimir Lifschitz [ 11 ] requires the reduct of a given LP w.r.t. a set defined as: = { ← 1, . . . , | ← 1, . . . , , not 1, . . . , not ∈ with {1, . . . , } ∩ = ∅}. A set of atoms ⊆ is a stable model of if it is the ⊆ -least model of , where a rule ← 1, . . . , is interpreted as the material implication 1 ∧ . . . ∧ → .

The following associated (sceptical) operator behaves as in the case of default logic; it satisfies inclusion, idempotence, cut, and supraclassicality (under the standard translation to classical logic), but generally fails compactness, monotonicity, cumulativity, and cautious monotonicity. Definition 2.2 ( Inference operator — Stable Models). Let SM( ) denote the set of all stable extensions of the logic program . The inference operator is defined as: C : 2 → 2, ↦→ C () = ⋂︀ SM( ∪)

3. Dung-style Argumentation

In 1995, Dung introduced one of the most influential argumentation formalisms which represent arguments and attacks as abstract entities – that is, neither the internal structure of arguments nor the reasons why one argument attacks another are taken into account [ 3 ]. Consequently, an Argumentation Frameworks (AF) is simply a directed graph (, ), where ⊆ is a set of arguments and ⊆ × a binary relation representing attacks. The main focus lies in resolving conflicts. For the purposes of this paper, we focus exclusively on stable semantics (see [12] for other semantics). A set ⊆ is a stable extension if (i) is conflict-free, and (ii) every argument not in is attacked by some argument in . Let ( ) denote the set of all stable extensions of an AF . As with Logic Programming, stable extensions are not guaranteed to exist; a framework may have none, exactly one, or multiple stable extensions. For instance, the following AF : yields two stable extensions, namely 1 = {, } and 2 = {, }. Which inference operator is suitable to adequately capture the dynamics of argumentation? In this initial paper, we draw inspiration from the inference operators already introduced for Default Logic and Logic Programming under stable model semantics. Default Logic–style Inference Operator In the case of Default Logic, the inference operator is parameterized by a set of defaults . This means that for each diferent set , we obtain a diferent operator C. Each such operator takes as input a set of (non-default) knowledge , and its output C( ) is defined as the intersection of all Reiter extensions, i.e., C( ) = ⋂︀ ℰ(, ). Transferring this concept to Dung-style Argumentation, we may parameterize an operator by a set of attacks and take as input a set of arguments . The output is then defined as the intersection of all stable extensions of the restricted AF (, |). This operator behaves quite interestingly, as it satisfies idempotence, cautious monotony, cut, and thus cumulativity, but generally fails inclusion, monotonicity, and compactness. We note that the corresponding credulous inference operator – i.e., taking the union of all stable extensions – satisfies the same properties as the sceptical one and, in addition, even satisfies compactness. Definition 3.1 ( Inference operator – Default Logic-style). Let ⊆ × be an attack relation. The associated (sceptical) inference operator is defined as: C : 2 → 2 , ↦→ C() = ⋂︀ ((, |)) Logic Programming–style Inference Operator In the case of logic programs, the inference operator is parameterized by a logic program . This means that for each diferent program , we obtain a diferent operator C . Each such operator takes as input a set of atoms and outputs C () = ⋂︀ ( ∪ ), i.e., the intersection of all stable models of ∪ . Transferring this concept in a straightforward way to the realm of Dung’s Argumentation Frameworks yields an operator parameterized by an AF = (, ), which takes as input a set of arguments . The output is then defined as the intersection of all stable extensions of the augmented framework ( ∪ , ).

Definition 3.2 ( Inference operator – Logic Programming-style). Let = (, ) be an AF. The associated (sceptical) inference operator is defined as: C : 2 → 2 , ↦→ C () = ⋂︀ (( ∪ , ))

Although both operator definitions look quite similar, their behaviour difers significantly. Whereas the Default Logic–style inference operator exhibits non-monotonic behaviour (as expected), its Logic Programming–style counterpart satisfies classical monotonicity. This may be surprising at first glance, but becomes intuitive upon closer inspection: adding arguments that introduce no new conflicts does not provide a reason to retract previously accepted information. Note that in the case of the Default Logic–style operator, additional attacks are implicitly introduced due to the presence of a background attack relation. In summary, the inference operator as defined above satisfies idempotence, compactness, monotonicity, and thus also cautious monotony, cut, and cumulativity, but it generally fails inclusion.

4. Conclusions and Future Lines

The present study admits instantiation through diferent acceptance modes, argumentation semantics, or even solely by considering abstract principles underlying argumentation semantics [13, 14].

One central question is how the presented operators are related. While the Default-style operator exhibits full non-monotonicity, as expected, the LP-style operator can be seen as a monotonic bridge logic, as termed by Makinson [ 8 ]. We note that identifying monotonic fragments within argumentation has already attracted some interest [15, 16, 17]. Finally, the presented operators do not satisfy inclusion. We believe this is an essential feature of any argumentation operator, as one cannot expect that all arguments they put forward will be accepted or pass unchallenged.

Acknowledgments

This work was supported by the German Research Foundation (DFG, BA 6170/3-1) and by the German Federal Ministry of Education and Research (BMBF, 01/S18026A-F) by funding the competence center for Big Data and AI “ScaDS.AI” Dresden/Leipzig. Leon van der Torre acknowledges the financial support of the Luxembourg National Research Fund (FNR) through the projects: The Epistemology of AI Systems (EAI) (C22/SC/17111440), DJ4ME – A DJ for Machine Ethics: the Dialogue Jiminy (O24/18989918/DJ4ME), Logical Methods for Deontic Explanations (LoDEx) (INTER/DFG/23/17415164/LoDEx) and Symbolic and Explainable Regulatory AI for Finance Innovation (SERAFIN) (C24/19003061/SERAFIN).

Declaration on Generative AI

The authors have not employed any Generative AI tools. [12] P. Baroni, M. Caminada, M. Giacomin, Abstract Argumentation Frameworks and Their Semantics, in: Handbook of Formal Argumentation, College Publications, 2018, pp. 159–236. [13] P. Baroni, M. Giacomin, On Principle-Based Evaluation of Extension-Based Argumentation Semantics, Artificial Intelligence 171 (2007) 675–700. URL: https://doi.org/10.1016/j.artint.2007.04.004. doi:10.1016/J.ARTINT.2007.04.004. [14] L. van der Torre, S. Vesic, The Principle-Based Approach to Abstract Argumentation Semantics,

FLAP 4 (2017). URL: http://www.collegepublications.co.uk/downloads/ifcolog00017.pdf. [15] R. Baumann, G. Brewka, Expanding Argumentation Frameworks: Enforcing and Monotonicity Results, in: P. Baroni, F. Cerutti, M. Giacomin, G. R. Simari (Eds.), Computational Models of Argument: Proceedings of COMMA 2010, Desenzano del Garda, Italy, September 8-10, 2010, volume 216 of Frontiers in Artificial Intelligence and Applications , IOS Press, 2010, pp. 75–86. URL: https://doi.org/10.3233/978-1-60750-619-5-75. doi:10.3233/978-1-60750-619-5-75. [16] C. Cayrol, F. D. de Saint-Cyr, M. Lagasquie-Schiex, Revision of an Argumentation System, in: G. Brewka, J. Lang (Eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the Eleventh International Conference, KR 2008, Sydney, Australia, September 16-19, 2008, AAAI Press, 2008, pp. 124–134. URL: http://www.aaai.org/Library/KR/2008/kr08-013.php. [17] R. Booth, S. Kaci, T. Rienstra, L. W. N. van der Torre, Monotonic and Nonmonotonic Inference for Abstract Argumentation, in: C. Boonthum-Denecke, G. M. Youngblood (Eds.), Proceedings of the Twenty-Sixth International Florida Artificial Intelligence Research Society Conference, FLAIRS 2013, St. Pete Beach, Florida, USA, May 22-24, 2013, AAAI Press, 2013. URL: http://www.aaai.org/ ocs/index.php/FLAIRS/FLAIRS13/paper/view/5863.

References

[1] D. M. Gabbay , Theoretical Foundations for Non-Monotonic Reasoning in Expert Systems , in: K. R. Apt (Ed.), Logics and Models of Concurrent Systems , Springer Berlin Heidelberg, Berlin, Heidelberg, 1985 , pp. 439 - 457 .

[2] O. Arieli , A. Borg , J. Heyninck , C. Straßer , Logic-Based Approaches to Formal Argumentation, FLAP 8 ( 2021 ) 1793 - 1898 . URL: https://collegepublications.co.uk/ifcolog/?00048.

[3] P. M. Dung , On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games , Artificial Intelligence 77 ( 1995 ) 321 - 357 .

[4] G. Brewka , S. Woltran , Abstract Dialectical Frameworks, in: F. Lin , U. Sattler , M. Truszczynski (Eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the Twelfth International Conference, KR 2010 , Toronto, Ontario, Canada, May 9- 13 , 2010 , AAAI Press, 2010 . URL: http: //aaai.org/ocs/index.php/KR/KR2010/paper/view/1294.

[5] A. Bondarenko , F. Toni , R. A. Kowalski , An Assumption-Based Framework for Non-Monotonic Reasoning, in: Logic Programming and Non-monotonic Reasoning , Proceedings of the Second International Workshop, Lisbon, Portugal, June 1993 , 1993 , pp. 171 - 189 .

[6] A. Tarski , Fundamentale Begrife der Methodologie der deduktiven Wissenschaften., Monatshefte für Mathematik und Physik 37 ( 1930 ) 361 - 404 .

[7] A. Tarski , Uber einige fundamentale Begrife der Methamathematik , Comptes rendus de la Societe des Sciences et des Lettres de Varsovien Classe XIX2Y ( 1930 ).

[8] D. Makinson , How to Go Nonmonotonic, Springer Netherlands, Dordrecht, 2005 , pp. 175 - 278 . URL: https://doi.org/10.1007/1-4020-3092- 4 _3. doi: 10 .1007/1-4020-3092- 4 _ 3 .

[9] S. Kraus , D. Lehmann , M. Magidor , Nonmonotonic Reasoning, Preferential Models and Cumulative Logics, Artificial Intelligence 44 ( 1990 ) 167 - 207 . URL: https://www.sciencedirect.com/science/ article/pii/0004370290901015. doi:https://doi.org/10.1016/ 0004 - 3702 ( 90 ) 90101 - 5 .

[10] R. Reiter , A Logic for Default Reasoning , Artificial Intelligence 13 ( 1980 ) 81 - 132 . URL: https:// www.sciencedirect.com/science/article/pii/0004370280900144. doi:https://doi.org/10.1016/ 0004 - 3702 ( 80 ) 90014 - 4 , Special Issue on Non-Monotonic Logic.

[11] M. Gelfond , V. Lifschitz , The Stable Model Semantics for Logic Programming, in: Logic Programming , Proceedings of the Fifth International Conference and Symposium , Seattle, Washington, USA, August 15- 19 , 1988 (2 Volumes), 1988 , pp. 1070 - 1080 .