×

Analyzing the computational complexity of abstract dialectical frameworks via approximation fixpoint theory. (English) Zbl 1346.68188

Summary: Abstract dialectical frameworks (ADFs) have recently been proposed as a versatile generalization of Dung’s abstract argumentation frameworks (AFs). In this paper, we present a comprehensive analysis of the computational complexity of ADFs. Our results show that while ADFs are one level up in the polynomial hierarchy compared to AFs, there is a useful subclass of ADFs which is as complex as AFs while arguably offering more modeling capacities. As a technical vehicle, we employ the approximation fixpoint theory of Denecker, Marek and Truszczyński, thus showing that it is also a useful tool for complexity analysis of operator-based semantics.

MSC:

68T27 Logic in artificial intelligence
68Q25 Analysis of algorithms and problem complexity
68T30 Knowledge representation

Software:

DIAMOND; Carneades
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alviano, Mario; Faber, Wolfgang, Stable model semantics of abstract dialectical frameworks revisited: a logic programming perspective, (Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015 (2015), IJCAI/AAAI), in press · Zbl 1365.68147
[2] Baroni, Pietro; Giacomin, Massimiliano, On principle-based evaluation of extension-based argumentation semantics, Artif. Intell., 171, 10-15, 675-700 (2007) · Zbl 1168.68559
[3] Baumann, Ringo, Splitting an argumentation framework, (Delgrande, James P.; Faber, Wolfgang, Proceedings of the Eleventh International Conference on Logic Programming and Nonmonotonic Reasoning. Proceedings of the Eleventh International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR. Proceedings of the Eleventh International Conference on Logic Programming and Nonmonotonic Reasoning. Proceedings of the Eleventh International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR, Lect. Notes Comput. Sci., vol. 6645 (2011), Springer), 40-53 · Zbl 1327.68240
[4] Baumann, Ringo; Dvořák, Wolfgang; Linsbichler, Thomas; Strass, Hannes; Woltran, Stefan, Compact argumentation frameworks, (Schaub, Torsten; Friedrich, Gerhard; O’Sullivan, Barry, Proceedings of the Twenty-First European Conference on Artificial Intelligence. Proceedings of the Twenty-First European Conference on Artificial Intelligence, ECAI (2014), IOS Press), 69-74 · Zbl 1366.68276
[5] Bench-Capon, Trevor J. M.; Dunne, Paul E., Argumentation in artificial intelligence, Artif. Intell., 171, 10-15, 619-641 (July 2007) · Zbl 1168.68560
[6] Bogaerts, Bart; Vennekens, Joost; Denecker, Marc, Grounded fixpoints and their applications in knowledge representation, Artif. Intell., 224, 51-71 (2015) · Zbl 1343.68233
[7] Bourbaki, Nicolas, Sur le théorème de Zorn, Arch. Math., 434-437 (1949) · Zbl 0045.32902
[8] Brewka, Gerhard; Gordon, Thomas F., Carneades and abstract dialectical frameworks: a reconstruction, (Baroni, Pietro; Cerutti, Federico; Giacomin, Massimiliano; Simari, Guillermo Ricardo, Proceedings of the Third International Conference on Computational Models of Argument. Proceedings of the Third International Conference on Computational Models of Argument, COMMA 2010. Proceedings of the Third International Conference on Computational Models of Argument. Proceedings of the Third International Conference on Computational Models of Argument, COMMA 2010, Front. Artif. Intell. Appl., vol. 216 (2010), IOS Press), 3-12
[9] Brewka, Gerhard; Woltran, Stefan, Abstract dialectical frameworks, (Lin, Fangzhen; Sattler, Ulrike; Truszczyński, Miroslaw, Proceedings of the Twelfth International Conference on Principles of Knowledge Representation and Reasoning. Proceedings of the Twelfth International Conference on Principles of Knowledge Representation and Reasoning, KR 2010 (2010), AAAI Press), 102-111
[10] Brewka, Gerhard; Dunne, Paul E.; Woltran, Stefan, Relating the semantics of abstract dialectical frameworks and standard AFs, (Walsh, Toby, Proceedings of the 22nd International Joint Conference on Artificial Intelligence. Proceedings of the 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011 (2011), IJCAI/AAAI), 780-785
[11] Brewka, Gerhard; Ellmauthaler, Stefan; Strass, Hannes; Wallner, Johannes P.; Woltran, Stefan, Abstract dialectical frameworks revisited, (Rossi, Francesca, Proceedings of the 23rd International Joint Conference on Artificial Intelligence. Proceedings of the 23rd International Joint Conference on Artificial Intelligence, IJCAI 2013 (2013), IJCAI/AAAI), 803-809
[12] Brewka, Gerhard; Polberg, Sylwia; Woltran, Stefan, Generalizations of Dung frameworks and their role in formal argumentation, Special Issue on Representation and Reasoning. Special Issue on Representation and Reasoning, IEEE Intell. Syst., 29, 1 (2013)
[13] Caminada, Martin W. A.; Amgoud, Leila, On the evaluation of argumentation formalisms, Artif. Intell., 171, 5-6, 286-310 (2007) · Zbl 1168.68562
[14] Caminada, Martin W. A.; Carnielli, Walter A.; Dunne, Paul E., Semi-stable semantics, J. Log. Comput., 22, 5, 1207-1254 (2012) · Zbl 1267.68223
[15] Coste-Marquis, Sylvie; Devred, Caroline; Marquis, Pierre, Symmetric argumentation frameworks, (Godo, Lluis, Proceedings of the Eighth European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty. Proceedings of the Eighth European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2005. Proceedings of the Eighth European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty. Proceedings of the Eighth European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2005, Lect. Notes Comput. Sci., vol. 3571 (2005), Springer), 317-328 · Zbl 1122.68642
[16] Darwiche, Adnan; Marquis, Pierre, A knowledge compilation map, J. Artif. Intell. Res., 17, 229-264 (2002) · Zbl 1045.68131
[17] Davey, B. A.; Priestley, H. A., Introduction to Lattices and Order (2002), Cambridge University Press · Zbl 1002.06001
[18] Denecker, Marc; Marek, Victor W.; 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
[19] Denecker, Marc; Marek, Victor W.; Truszczyński, Miroslaw, Uniform semantic treatment of default and autoepistemic logics, Artif. Intell., 143, 1, 79-122 (2003) · Zbl 1010.03021
[20] 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
[21] Diller, Martin; Wallner, Johannes P.; Woltran, Stefan, Reasoning in abstract dialectical frameworks using quantified Boolean formulas, (Parsons, Simon; Oren, Nir; Reed, Chris, Proceedings of the Fifth International Conference on Computational Models of Argument. Proceedings of the Fifth International Conference on Computational Models of Argument, COMMA 2014. Proceedings of the Fifth International Conference on Computational Models of Argument. Proceedings of the Fifth International Conference on Computational Models of Argument, COMMA 2014, Front. Artif. Intell. Appl., vol. 266 (2014), IOS Press), 241-252
[22] Dimopoulos, Yannis; Torres, Alberto, Graph theoretical structures in logic programs and default theories, Theor. Comput. Sci., 170, 1-2, 209-244 (1996) · Zbl 0874.68190
[23] Dimopoulos, Yannis; Nebel, Bernhard; Toni, Francesca, On the computational complexity of assumption-based argumentation for default reasoning, Artif. Intell., 141, 1/2, 57-78 (2002) · Zbl 1043.68097
[24] Dung, Phan Minh, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and \(n\)-person games, Artif. Intell., 77, 2, 321-358 (1995) · Zbl 1013.68556
[25] Dung, Phan Minh; Mancarella, Paolo; Toni, Francesca, Computing ideal sceptical argumentation, Artif. Intell., 171, 10, 642-674 (2007) · Zbl 1168.68564
[26] Dunne, Paul E., The computational complexity of ideal semantics, Artif. Intell., 173, 18, 1559-1591 (2009) · Zbl 1185.68666
[27] Dunne, Paul E.; Bench-Capon, Trevor J. M., Coherence in finite argument systems, Artif. Intell., 141, 1/2, 187-203 (2002) · Zbl 1043.68098
[28] Dunne, Paul E.; Wooldridge, Michael, Complexity of abstract argumentation, (Simari, Guillermo; Rahwan, Iyad, Argumentation in Artificial Intelligence (2009), Springer), 85-104
[29] Dvořák, Wolfgang; Ordyniak, Sebastian; Szeider, Stefan, Augmenting tractable fragments of abstract argumentation, Artif. Intell., 186, 157-173 (2012) · Zbl 1251.68225
[30] Dvořák, Wolfgang; Järvisalo, Matti; Wallner, Johannes P.; Woltran, Stefan, Complexity-sensitive decision procedures for abstract argumentation, Artif. Intell., 206, 53-78 (2014) · Zbl 1334.68206
[31] Egly, Uwe; Gaggl, Sarah A.; Woltran, Stefan, Answer-set programming encodings for argumentation frameworks, Argument. Comput., 1, 2, 147-177 (2010) · Zbl 1226.68018
[32] Ellmauthaler, Stefan; Strass, Hannes, The DIAMOND system for computing with abstract dialectical frameworks, (Parsons, Simon; Oren, Nir; Reed, Chris, Proceedings of the Fifth International Conference on Computational Models of Argument. Proceedings of the Fifth International Conference on Computational Models of Argument, COMMA 2014. Proceedings of the Fifth International Conference on Computational Models of Argument. Proceedings of the Fifth International Conference on Computational Models of Argument, COMMA 2014, Front. Artif. Intell. Appl., vol. 266 (2014), IOS Press), 233-240
[33] Gaggl, Sarah A.; Strass, Hannes, Decomposing abstract dialectical frameworks, (Parsons, Simon; Oren, Nir; Reed, Chris, Proceedings of the Fifth International Conference on Computational Models of Argument. Proceedings of the Fifth International Conference on Computational Models of Argument, COMMA 2014. Proceedings of the Fifth International Conference on Computational Models of Argument. Proceedings of the Fifth International Conference on Computational Models of Argument, COMMA 2014, Front. Artif. Intell. Appl., vol. 266 (2014), IOS Press), 281-292
[34] Gaggl, Sarah A.; Rudolph, Sebastian; Strass, Hannes, On the computational complexity of naive-based semantics for abstract dialectical frameworks, (Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015 (2015), IJCAI/AAAI), in press · Zbl 1476.68251
[35] 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
[36] Linsbichler, Thomas, Splitting abstract dialectical frameworks, (Parsons, Simon; Oren, Nir; Reed, Chris, Proceedings of the Fifth International Conference on Computational Models of Argument. Proceedings of the Fifth International Conference on Computational Models of Argument, COMMA 2014. Proceedings of the Fifth International Conference on Computational Models of Argument. Proceedings of the Fifth International Conference on Computational Models of Argument, COMMA 2014, Front. Artif. Intell. Appl., vol. 266 (2014), IOS Press), 357-368
[37] Papadimitriou, Christos H., Computational Complexity (1994), Addison-Wesley · Zbl 0833.68049
[38] Polberg, Sylwia, Extension-based semantics of abstract dialectical frameworks, (Konieczny, Sébastien; Tompits, Hans, Proceedings of the Fifteenth International Workshop on Non-Monotonic Reasoning. Proceedings of the Fifteenth International Workshop on Non-Monotonic Reasoning, NMR 2014 (2014)), 273-282 · Zbl 1343.68228
[39] Polberg, Sylwia; Wallner, Johannes P.; Woltran, Stefan, Admissibility in the abstract dialectical framework, (Leite, João; Son, Tran Cao; Torroni, Paolo; van der Torre, Leon; Woltran, Stefan, Proceedings of the 14th International Workshop on Computational Logic in Multi-Agent Systems. Proceedings of the 14th International Workshop on Computational Logic in Multi-Agent Systems, CLIMA 2013. Proceedings of the 14th International Workshop on Computational Logic in Multi-Agent Systems. Proceedings of the 14th International Workshop on Computational Logic in Multi-Agent Systems, CLIMA 2013, Lect. Notes Artif. Intell., vol. 8143 (2013), Springer), 102-118 · Zbl 1401.68310
[40] Strass, Hannes, Approximating operators and semantics for abstract dialectical frameworks, Artif. Intell., 205, 39-70 (2013) · Zbl 1334.68212
[41] Strass, Hannes, Instantiating knowledge bases in abstract dialectical frameworks, (Leite, João; Son, Tran Cao; Torroni, Paolo; van der Torre, Leon; Woltran, Stefan, 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 2013. 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 2013, Lect. Notes Artif. Intell., vol. 8143 (2013), Springer), 86-101 · Zbl 1343.68229
[42] Strass, Hannes, The relative expressiveness of abstract argumentation and logic programming, (Koenig, Sven; Bonet, Blai, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI 2015 (2015)), 1625-1631
[43] Strass, Hannes, Instantiating rule-based defeasible theories in abstract dialectical frameworks and beyond, J. Log. Comput. (2015) · Zbl 1343.68230
[44] Strass, Hannes; Wallner, Johannes P., Analyzing the computational complexity of abstract dialectical frameworks via approximation fixpoint theory, (Baral, Chitta; De Giacomo, Giuseppe; Eiter, Thomas, Proceedings of the Fourteenth International Conference on the Principles of Knowledge Representation and Reasoning. Proceedings of the Fourteenth International Conference on the Principles of Knowledge Representation and Reasoning, KR 2014 (2014), AAAI Press), 101-110
[45] Van Gijzel, Bas; Prakken, Henry, Relating Carneades with abstract argumentation, (Walsh, Toby, Proceedings of the 22nd International Joint Conference on Artificial Intelligence. Proceedings of the 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011 (2011), IJCAI/AAAI), 1113-1119
[46] Vennekens, Joost; Gilis, David; Denecker, Marc, Splitting an operator: algebraic modularity results for logics with fixpoint semantics, ACM Trans. Comput. Log., 7, 4, 765-797 (2006) · Zbl 1367.68295
[47] Wyner, Adam; Bench-Capon, Trevor J. M.; Dunne, Paul E., On the instantiation of knowledge bases in abstract argumentation frameworks, (Leite, João; Cao Son, Tran; Torroni, Paolo; van der Torre, Leon; Woltran, Stefan, 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 2013. 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 2013, Lect. Notes Artif. Intell., vol. 8143 (2013), Springer), 34-50 · 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.