×

zbMATH — the first resource for mathematics

Complexity-sensitive decision procedures for abstract argumentation. (English) Zbl 1334.68206
Summary: Abstract argumentation frameworks (AFs) provide the basis for various reasoning problems in the area of Artificial Intelligence. Efficient evaluation of AFs has thus been identified as an important research challenge. So far, implemented systems for evaluating AFs have either followed a straight-forward reduction-based approach or been limited to certain tractable classes of AFs. In this work, we present a generic approach for reasoning over AFs, based on the novel concept of complexity-sensitivity. Establishing the theoretical foundations of this approach, we derive several new complexity results for preferred, semi-stable and stage semantics which complement the current complexity landscape for abstract argumentation, providing further understanding on the sources of intractability of AF reasoning problems. The introduced generic framework exploits decision procedures for problems of lower complexity whenever possible. This allows, in particular, instantiations of the generic framework via harnessing in an iterative way current sophisticated Boolean satisfiability (SAT) solver technology for solving the considered AF reasoning problems. First experimental results show that the SAT-based instantiation of our novel approach outperforms existing systems.

MSC:
68T27 Logic in artificial intelligence
68Q25 Analysis of algorithms and problem complexity
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Dung, P. M., On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artificial Intelligence, 77, 2, 321-358, (1995) · Zbl 1013.68556
[2] Dunne, P. E.; Bench-Capon, T. J.M., Coherence in finite argument systems, Artificial Intelligence, 141, 1/2, 187-203, (2002) · Zbl 1043.68098
[3] Dvořák, W.; Woltran, S., Complexity of semi-stable and stage semantics in argumentation frameworks, Inform. Process. Lett., 110, 11, 425-430, (2010) · Zbl 1229.68041
[4] Coste-Marquis, S.; Devred, C.; Marquis, P., Symmetric argumentation frameworks, (Proceedings of the 8th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2005, Lecture Notes in Comput. Sci., vol. 3571, (2005), Springer), 317-328 · Zbl 1122.68642
[5] Dunne, P. E., Computational properties of argument systems satisfying graph-theoretic constraints, Artificial Intelligence, 171, 10-15, 701-729, (2007) · Zbl 1168.68565
[6] Dvořák, W.; Szeider, S.; Woltran, S., Reasoning in argumentation frameworks of bounded clique-width, (Proceedings of the 3rd International Conference on Computational Models of Argument, COMMA 2010, Frontiers Artificial Intelligence Appl., vol. 216, (2010), IOS Press), 219-230
[7] Dvořák, W.; Pichler, R.; Woltran, S., Towards fixed-parameter tractable algorithms for abstract argumentation, Artificial Intelligence, 186, 1-37, (2012) · Zbl 1251.68226
[8] Dvořák, W.; Ordyniak, S.; Szeider, S., Augmenting tractable fragments of abstract argumentation, Artificial Intelligence, 186, 157-173, (2012) · Zbl 1251.68225
[9] Truszczynski, M., Trichotomy and dichotomy results on the complexity of reasoning with disjunctive logic programs, Theory Pract. Log. Program., 11, 6, 881-904, (2011) · Zbl 1242.68052
[10] Marques-Silva, J. P.; Sakallah, K. A., GRASP: A search algorithm for propositional satisfiability, IEEE Trans. Comput., 48, 5, 506-521, (1999) · Zbl 1392.68388
[11] Eén, N.; Sörensson, N., An extensible SAT-solver, (Proceedings of the 6th International Conference on Theory and Applications of Satisfiability Testing, SAT 2003, Lecture Notes in Comput. Sci., vol. 2919, (2004), Springer), 502-518 · Zbl 1204.68191
[12] Clarke, E. M.; Grumberg, O.; Jha, S.; Lu, Y.; Veith, H., Counterexample-guided abstraction refinement for symbolic model checking, J. ACM, 50, 5, 752-794, (2003) · Zbl 1325.68145
[13] Clarke, E. M.; Gupta, A.; Strichman, O., SAT-based counterexample-guided abstraction refinement, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 23, 7, 1113-1123, (2004)
[14] Eiter, T.; Gottlob, G., On the computational cost of disjunctive logic programming: propositional case, Ann. Math. Artif. Intell., 15, 3-4, 289-323, (1995) · Zbl 0858.68016
[15] Lierler, Y., Cmodels - SAT-based disjunctive answer set solver, (Proceedings of the 8th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2005, Lecture Notes in Comput. Sci., vol. 3662, (2005), Springer), 447-451
[16] Besnard, P.; Doutre, S., Checking the acceptability of a set of arguments, (Proceedings of the 10th International Workshop on Non-Monotonic Reasoning, NMR 2004, (2004)), 59-64
[17] Egly, U.; Gaggl, S. A.; Woltran, S., Answer-set programming encodings for argumentation frameworks, Argum. Comput., 1, 2, 147-177, (2010)
[18] Dvořák, W.; Gaggl, S. A.; Wallner, J. P.; Woltran, S., Making use of advances in answer-set programming for abstract argumentation systems, (Post-Conference Proceedings of the 19th International Conference on Applications of Declarative Programming and Knowledge Management, INAP 2011, and the 25th Workshop on Logic Programming, WLP 2011, Lecture Notes in Comput. Sci., vol. 7773, (2013), Springer), in press. Preliminary version
[19] Baroni, P.; Giacomin, M., Semantics of abstract argument systems, (Rahwan, I.; Simari, G., Argumentation in Artificial Intelligence, (2009), Springer), 25-44
[20] Baroni, P.; Caminada, M.; Giacomin, M., An introduction to argumentation semantics, Knowl. Eng. Rev., 26, 4, 365-410, (2011)
[21] Dimopoulos, Y.; Torres, A., Graph theoretical structures in logic programs and default theories, Theoret. Comput. Sci., 170, 1-2, 209-244, (1996) · Zbl 0874.68190
[22] Dunne, P. E.; Caminada, M., Computational complexity of semi-stable semantics in abstract argumentation frameworks, (Proceedings of the 11th European Conference on Logics in Artificial Intelligence, JELIA 2008, Lecture Notes in Comput. Sci., vol. 5293, (2008), Springer), 153-165 · Zbl 1178.68557
[23] Dvořák, W.; Woltran, S., On the intertranslatability of argumentation semantics, J. Artificial Intelligence Res., 41, 445-475, (2011) · Zbl 1234.68369
[24] Bang-Jensen, J.; Gutin, G., Digraphs: theory, algorithms and applications, Springer Monogr. Math., (2010), Springer · Zbl 1210.05001
[25] Dunne, P. E.; Wooldridge, M., Complexity of abstract argumentation, (Simari, G.; Rahwan, I., Argumentation in Artificial Intelligence, (2009), Springer), 85-104
[26] Dunne, P. E., The computational complexity of ideal semantics, Artificial Intelligence, 173, 18, 1559-1591, (2009) · Zbl 1185.68666
[27] Valiant, L. G.; Vazirani, V. V., NP is as easy as detecting unique solutions, Theoret. Comput. Sci., 47, 3, 85-93, (1986) · Zbl 0621.68030
[28] Caminada, M.; Gabbay, D., A logical account of formal argumentation, Studia Logica, 93, 2-3, 109-145, (2009) · Zbl 1188.03011
[29] Dvořák, W.; Gaggl, S. A.; Szeider, S.; Woltran, S., The added value of argumentation, (Benchmark Libraries for Argumentation, Agreement Technologies, vol. 8, (2013)), 389-393
[30] Gebser, M.; Kaminski, R.; Schaub, T., Complex optimization in answer set programming, Theory Pract. Log. Program., 11, 4-5, 821-839, (2011) · Zbl 1222.68059
[31] Drescher, C.; Gebser, M.; Grote, T.; Kaufmann, B.; König, A.; Ostrowski, M.; Schaub, T., Conflict-driven disjunctive answer set solving, (Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning, KR 2008, (2008), AAAI Press), 422-432
[32] Gebser, M.; Kaminski, R.; König, A.; Schaub, T., Advances in gringo series 3, (Proceedings of the 11th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2011, Lecture Notes in Comput. Sci., vol. 6645, (2011), Springer), 345-351
[33] Sebastiani, R., Lazy satisfiability modulo theories, J. Satisf. Boolean Model. Comput., 3, 3-4, 141-224, (2007) · Zbl 1145.68501
[34] de Moura, L.; Ruess, H.; Sorea, M., Lazy theorem proving for bounded model checking over infinite domains, (Proceedings of the 18th International Conference on Automated Deduction, CADE-18, Lecture Notes in Comput. Sci., vol. 2392, (2002), Springer), 438-455 · Zbl 1072.68602
[35] Barrett, C. W.; Dill, D. L.; Stump, A., Checking satisfiability of first-order formulas by incremental translation to SAT, (Proceedings of the 14th International Conference on Computer Aided Verification, CAV 2002, Lecture Notes in Comput. Sci., vol. 2404, (2002), Springer), 236-249 · Zbl 1010.68531
[36] Flanagan, C.; Joshi, R.; Ou, X.; Saxe, J. B., Theorem proving using lazy proof explication, (Proceedings of the 15th International Conference on Computer Aided Verification, CAV 2003, Lecture Notes in Comput. Sci., vol. 2725, (2003), Springer), 355-367 · Zbl 1278.68259
[37] Wintersteiger, C. M.; Hamadi, Y.; de Moura, L., Efficiently solving quantified bit-vector formulas, (Proceedings of the 10th International Conference on Formal Methods in Computer-Aided Design, FMCAD 2010, (2010), IEEE), 239-246
[38] Monniaux, D., Quantifier elimination by lazy model enumeration, (Proceedings of the 22nd International Conference on Computer Aided Verification, CAV 2010, Lecture Notes in Comput. Sci., vol. 6174, (2010), Springer), 585-599
[39] Janota, M.; Grigore, R.; Marques-Silva, J., Counterexample guided abstraction refinement algorithm for propositional circumscription, (Proceedings of the 12th European Conference on Logics in Artificial Intelligence, JELIA 2010, Lecture Notes in Comput. Sci., vol. 6341, (2010), Springer), 195-207 · Zbl 1306.68190
[40] Janota, M.; Marques-Silva, J. P., Abstraction-based algorithm for 2QBF, (Proceedings of the 14th International Conference on Theory and Applications of Satisfiability Testing, SAT 2011, Lecture Notes in Comput. Sci., vol. 6695, (2011), Springer), 230-244 · Zbl 1330.68115
[41] Janota, M.; Klieber, W.; Marques-Silva, J.; Clarke, E. M., Solving QBF with counterexample guided refinement, (Proceedings of the 15th International Conference on Theory and Applications of Satisfiability Testing, SAT 2012, Lecture Notes in Comput. Sci., vol. 7317, (2012), Springer), 114-128 · Zbl 1273.68178
[42] Arieli, O.; Caminada, M. W.A., A QBF-based formalization of abstract argumentation semantics, J. Appl. Log., 11, 2, 229-252, (2013) · Zbl 1284.68533
[43] Egly, U.; Woltran, S., Reasoning in argumentation frameworks using quantified Boolean formulas, (Proceedings of the 1st International Conference on Computational Models of Argument, OMMA 2006, Frontiers Artificial Intelligence Appl., vol. 144, (2006), IOS Press), 133-144
[44] Amgoud, L.; Devred, C., Argumentation frameworks as constraint satisfaction problems, (Proceedings of the 5th International Conference on Scalable Uncertainty Management, SUM 2011, Lecture Notes in Comput. Sci., vol. 6929, (2011), Springer), 110-122
[45] Bistarelli, S.; Campli, P.; Santini, F., Finding partitions of arguments with dungʼs properties via scsps, (Proceedings of the 2011 ACM Symposium on Applied Computing, SAC 2011, (2011), ACM), 913-919
[46] Verheij, B., A labeling approach to the computation of credulous acceptance in argumentation, (Proceedings of the 20th International Joint Conference on Artificial Intelligence, IJCAI, (2007)), 623-628
[47] Modgil, S.; Caminada, M., Proof theories and algorithms for abstract argumentation frameworks, (Argumentation in Artificial Intelligence, (2009), Springer), 105-132
[48] Podlaszewski, M.; Caminada, M.; Pigozzi, G., An implementation of basic argumentation components, (Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), IFAAMAS, 2011, (2011)), 1307-1308
[49] Doutre, S.; Mengin, J., Preferred extensions of argumentation frameworks: query answering and computation, (Goré, R.; Leitsch, A.; Nipkow, T., Proceedings Automated Reasoning, First International Joint Conference, IJCAR 2001, Siena, Italy, June 18-23, 2001, Lecture Notes in Comput. Sci., vol. 2083, (2001), Springer), 272-288 · Zbl 0990.68541
[50] Nofal, S.; Dunne, P. E.; Atkinson, K., On preferred extension enumeration in abstract argumentation, (Proceedings of the 4th International Conference on Computational Models of Argument, COMMA 2012, Frontiers Artificial Intelligence Appl., vol. 245, (2012), IOS Press), 205-216
[51] Baumann, R., Splitting an argumentation framework, (Proceedings of the 11th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2011, Lecture Notes in Comput. Sci., vol. 6645, (2011), Springer), 40-53 · Zbl 1327.68240
[52] Baumann, R.; Brewka, G.; Wong, R., Splitting argumentation frameworks: an empirical evaluation, (Revised Selected Papers of the 1st International Workshop on Theories and Applications of Formal Argumentation, TAFA 2011, Lecture Notes in Comput. Sci., vol. 7132, (2012), Springer), 17-31
[53] Baumann, R.; Brewka, G.; Dvořák, W.; Woltran, S., Parameterized splitting: A simple modification-based approach, (Erdem, E.; Lee, J.; Lierler, Y.; Pearce, D., Correct Reasoning - Essays on Logic-Based AI in Honour of Vladimir Lifschitz, Lecture Notes in Comput. Sci., vol. 7265, (2012), Springer), 57-71 · Zbl 1357.68026
[54] Dvořák, W.; Pichler, R.; Woltran, S., Towards fixed-parameter tractable algorithms for abstract argumentation, Artificial Intelligence, 186, 1-37, (2012) · Zbl 1251.68226
[55] Dvořák, W.; Morak, M.; Nopp, C.; Woltran, S., A dynamic programming reasoner for abstract argumentation, (Post-Conference Proceedings of the 19th International Conference on Applications of Declarative Programming and Knowledge Management, INAP 2011, and the 25th Workshop on Logic Programming, WLP 2011, Lecture Notes in Comput. Sci., vol. 7773, (2013), Springer), in press. Preliminary version
[56] Nofal, S.; Dunne, P. E.; Atkinson, K., Towards average-case algorithms for abstract argumentation, (Proceedings of the 4th International Conference on Agents and Artificial Intelligence, ICAART 2012, Artificial Intelligence, vol. 1, (2012), SciTePress), 225-230
[57] Dvořák, W.; Järvisalo, M.; Wallner, J. P.; Woltran, S., Complexity-sensitive decision procedures for abstract argumentation, (Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning, KR 2012, (2012), AAAI Press), 54-64
[58] Brewka, G.; Woltran, S., Abstract dialectical frameworks, (Proceedings of the 12th International Conference on Principles of Knowledge Representation and Reasoning, KR 2010, (2010), AAAI Press), 102-111
[59] Amgoud, L.; Cayrol, C.; Lagasquie, M.-C.; Livet, P., On bipolarity in argumentation frameworks, Int. J. Intell. Syst., 23, 1-32, (2008) · Zbl 1151.68049
[60] Modgil, S., Reasoning about preferences in argumentation frameworks, Artificial Intelligence, 173, 9-10, 901-934, (2009) · Zbl 1192.68663
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.