×

Approximating operators and semantics for abstract dialectical frameworks. (English) Zbl 1334.68212

Summary: We provide a systematic in-depth study of the semantics of abstract dialectical frameworks (ADFs), a recent generalisation of Dung’s abstract argumentation frameworks. This is done by associating with an ADF its characteristic one-step consequence operator and defining various semantics for ADFs as different fixpoints of this operator. We first show that several existing semantical notions are faithfully captured by our definition, then proceed to define new ADF semantics and show that they are proper generalisations of existing argumentation semantics from the literature. Most remarkably, this operator-based approach allows us to compare ADFs to related nonmonotonic formalisms like Dung argumentation frameworks and propositional logic programs. We use polynomial, faithful and modular translations to relate the formalisms, and our results show that both abstract argumentation frameworks and abstract dialectical frameworks are at most as expressive as propositional normal logic programs.

MSC:

68T27 Logic in artificial intelligence
68N17 Logic programming

Software:

Carneades
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Besnard, Philippe; Doutre, Sylvie, Characterization of semantics for argument systems, (Didier Dubois; Welty, Christopher A.; Williams, Mary-Anne, Proceedings of the Ninth International Conference on Principles of Knowledge Representation and Reasoning. Proceedings of the Ninth International Conference on Principles of Knowledge Representation and Reasoning, KR2004 (2004), AAAI Press), 183-193
[2] Brewka, Gerhard; Gordon, Thomas F., Carneades and abstract dialectical frameworks: a reconstruction, (Computational Models of Argument: Proceedings of COMMA 2010. Computational Models of Argument: Proceedings of COMMA 2010, Frontiers in Artificial Intelligence and Applications, vol. 216 (September 2010), IOS Press), 3-12
[3] Brewka, Gerhard; Woltran, Stefan, Abstract dialectical frameworks, (Proceedings of the Twelfth International Conference on the Principles of Knowledge Representation and Reasoning (KR) (2010)), 102-111
[4] Brewka, Gerhard; Dunne, Paul E.; Woltran, Stefan, Relating the semantics of abstract dialectical frameworks and standard AFs, (Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (2011)), 780-785
[5] Brewka, Gerhard; Ellmauthaler, Stefan; Strass, Hannes; Wallner, Johannes Peter; Woltran, Stefan, Abstract dialectical frameworks revisited, (Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (August 2013), AAAI Press), 803-809
[6] Caminada, Martin, On the issue of reinstatement in argumentation, (Proceedings of the Tenth European Conference on Logics in Artificial Intelligence. Proceedings of the Tenth European Conference on Logics in Artificial Intelligence, Lecture Notes in Computer Science, vol. 4160 (September 2006), Springer), 111-123 · Zbl 1152.68600
[7] Caminada, Martin, An algorithm for stage semantics, (Computational Models of Argument: Proceedings of COMMA 2010 (2010)), 147-158
[8] Caminada, Martin; Amgoud, Leila, On the evaluation of argumentation formalisms, Artif. Intell., 171, 5-6, 286-310 (2007) · Zbl 1168.68562
[9] Cayrol, Claudette; Lagasquie-Schiex, Marie-Christine, Bipolar abstract argumentation systems, (Simari, Guillermo; Rahwan, Iyad, Argumentation in Artificial Intelligence (2009), Springer), 65-84
[10] Clark, Keith L., Negation as failure, (Gallaire, Hervé; Minker, Jack, Logic and Data Bases (1978), Plenum Press), 293-322
[11] Denecker, Marc; Marek, Victor; Truszczyński, Miroslaw, Approximations, stable operators, well-founded fixpoints and applications in nonmonotonic reasoning, (Logic-Based Artificial Intelligence (2000), Kluwer Academic Publishers), 127-144 · Zbl 0988.68183
[12] Denecker, Marc; Marek, V. Wiktor; Truszczyński, Miroslaw, Uniform semantic treatment of default and autoepistemic logics, Artif. Intell., 143, 1, 79-122 (2003) · Zbl 1010.03021
[13] Denecker, Marc; Marek, Victor W.; Truszczyński, Miroslaw, Ultimate approximation and its application in nonmonotonic knowledge representation systems, Inf. Comput., 192, 1, 84-121 (2004) · Zbl 1074.68069
[14] Phan; Dung, Minh, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and \(n\)-person games, Artif. Intell., 77, 321-358 (1995) · Zbl 1013.68556
[15] Egly, Uwe; Gaggl, Sarah Alice; Woltran, Stefan, Answer-set programming encodings for argumentation frameworks, Argument Comput., 1, 2, 147-177 (2010) · Zbl 1226.68018
[16] Eiter, Thomas; Fink, Michael; Moura, João, Paracoherent answer set programming, (Proceedings of the Twelfth International Conference on Principles of Knowledge Representation and Reasoning (May 2010)) · Zbl 1351.68259
[17] Ellmauthaler, Stefan; Wallner, Johannes Peter, Evaluating abstract dialectical frameworks with ASP, (Computational Models of Argument: Proceedings of COMMA 2012 (2012)), 505-506
[18] Fitting, Melvin, Fixpoint semantics for logic programming: a survey, Theor. Comput. Sci., 278, 1-2, 25-51 (2002) · Zbl 1002.68023
[19] Gabbay, Dov M.; dʼAvila Garcez, Artur S., Logical modes of attack in argumentation networks, Stud. Log., 93, 2-3, 199-230 (2009) · Zbl 1185.68671
[20] Gelfond, Michael; Lifschitz, Vladimir, The stable model semantics for logic programming, (Proceedings of the International Conference on Logic Programming. Proceedings of the International Conference on Logic Programming, ICLP (1988), The MIT Press), 1070-1080
[21] Gordon, Thomas F.; Prakken, Henry; Walton, Douglas, The Carneades model of argument and burden of proof, Artif. Intell., 171, 10-15, 875-896 (2007) · Zbl 1168.68566
[22] Gottlob, Georg, Translating default logic into standard autoepistemic logic, J. ACM, 42, 4, 711-740 (1995) · Zbl 0884.03025
[23] Grossi, Davide, Fixpoints and iterated updates in abstract argumentation, (Proceedings of the Thirteenth International Conference on the Principles of Knowledge Representation and Reasoning (KR) (2012), AAAI Press), 65-74
[24] Jakobovits, Hadassa; Vermeir, Dirk, Robust semantics for argumentation frameworks, J. Log. Comput., 9, 2, 215-261 (1999) · Zbl 0933.68088
[25] Janhunen, Tomi, On the intertranslatability of non-monotonic logics, Ann. Math. Artif. Intell., 27, 1-4, 79-128 (1999) · Zbl 0941.03028
[26] Konolige, Kurt, On the relation between default and autoepistemic logic, Artif. Intell., 35, 3, 343-382 (1988) · Zbl 0647.68088
[27] Wiktor Marek, V.; Truszczyński, Miroslaw, Stable semantics for logic programs and default theories, (North American Conference on Logic Programming (1989), The MIT Press), 243-256
[28] Modgil, Sanjay, Reasoning about preferences in argumentation frameworks, Artif. Intell., 173, 9-10, 901-934 (2009) · Zbl 1192.68663
[29] Moore, Robert, Semantical considerations of nonmonotonic logic, Artif. Intell., 25, 1, 75-94 (1985) · Zbl 0569.68079
[30] Nielsen, Søren H.; Parsons, Simon, A generalization of Dungʼs abstract framework for argumentation: Arguing with sets of attacking arguments, (Argumentation in Multi-Agent Systems. Argumentation in Multi-Agent Systems, LNCS, vol. 4766 (2006), Springer), 54-73 · Zbl 1429.68266
[31] Nieves, Juan Carlos; Osorio, Mauricio; Zepeda, Claudia, A schema for generating relevant logic programming semantics and its applications in argumentation theory, Fundam. Inform., 106, 2-4, 295-319 (2011) · Zbl 1244.68073
[32] Nogueira, Monica; Balduccini, Marcello; Gelfond, Michael; Watson, Richard; Barry, Matthew, An A-Prolog decision support system for the Space Shuttle, (Provetti, Alessandro; Tran Cao Son, Answer Set Programming (2001))
[33] Prakken, Henry, An abstract framework for argumentation with structured arguments, Argument Comput., 1, 2, 93-124 (2010) · Zbl 0866.03018
[34] Prakken, Henry; Sartor, Giovanni, A system for defeasible argumentation, with defeasible priorities, (Artificial Intelligence Today. Artificial Intelligence Today, LNAI (1999), Springer-Verlag: Springer-Verlag Berlin Heidelberg), 365-379 · Zbl 0956.68536
[35] Reiter, Raymond, A logic for default reasoning, Artif. Intell., 13, 81-132 (1980) · Zbl 0435.68069
[36] Saccà, Domenico; Zaniolo, Carlo, Deterministic and non-deterministic stable models, J. Log. Comput., 7, 5, 555-579 (1997) · Zbl 0883.68031
[37] Strass, Hannes, Instantiating knowledge bases in Abstract Dialectical Frameworks, (Proceedings of the Fourteenth International Workshop on Computational Logic in Multi-Agent Systems. Proceedings of the Fourteenth International Workshop on Computational Logic in Multi-Agent Systems, CLIMA XIV. Proceedings of the Fourteenth International Workshop on Computational Logic in Multi-Agent Systems. Proceedings of the Fourteenth International Workshop on Computational Logic in Multi-Agent Systems, CLIMA XIV, LNCS, vol. 8143 (September 2013), Springer), 86-101 · Zbl 1343.68229
[38] Tarski, Alfred, A lattice-theoretical fixpoint theorem and its applications, Pac. J. Math., 5, 2, 285-309 (1955) · Zbl 0064.26004
[39] Toni, Francesca; Sergot, Marek, Argumentation and answer set programming, (Balduccini, M.; Son, T., Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning: Essays in Honor of Michael Gelfond. Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning: Essays in Honor of Michael Gelfond, LNAI, vol. 6565 (2011), Springer), 164-180 · Zbl 1326.68279
[40] Van Gijzel, Bas; Prakken, Henry, Relating Carneades with abstract argumentation, (Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, vol. 2 (2011), AAAI Press), 1113-1119
[41] Verheij, Bart, Two approaches to dialectical argumentation: admissible sets and argumentation stages, (Meyer, J.-J. Ch.; van der Gaag, L. C., Proceedings of the Eighth Dutch Conference on Artificial Intelligence. Proceedings of the Eighth Dutch Conference on Artificial Intelligence, NAICʼ96 (1996)), 357-368
[42] Wakaki, Toshiko; Nitta, Katsumi, Computing argumentation semantics in answer set programming, (Proceedings of the Annual Conference of Japanese Society for Artificial Intelligence (JSAI) (2008)), 254-269
[43] Wu, Yining; Caminada, Martin; Gabbay, Dov M., Complete extensions in argumentation coincide with 3-valued stable models in logic programming, Stud. Log., 93, 2-3, 383-403 (2009) · Zbl 1189.68127
[44] Wyner, Adam; Bench-Capon, Trevor; Dunne, Paul, Instantiating knowledge bases in abstract argumentation frameworks, (Proceedings of the AAAI Fall Symposium - The Uses of Computational Argumentation (2009)) · Zbl 1401.68313
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.