Hostname: page-component-78c5997874-v9fdk Total loading time: 0 Render date: 2024-11-05T23:26:29.641Z Has data issue: false hasContentIssue false
  • English
  • Français

Solving Advanced Argumentation Problems with Answer Set Programming

Published online by Cambridge University Press:  15 January 2020

GERHARD BREWKA ,
MARTIN DILLER Open the ORCID record for MARTIN DILLER [Opens in a new window] ,
GEORG HEISSENBERGER ,
THOMAS LINSBICHLER  and
STEFAN WOLTRAN
GERHARD BREWKA
Affiliation:
Universität Leipzig, Leipzig, Germany
MARTIN DILLER
Affiliation:
TU Dresden, Dresden, Germany
GEORG HEISSENBERGER
Affiliation:
TU Wien, Vienna, Austria
THOMAS LINSBICHLER
Affiliation:
TU Wien, Vienna, Austria
STEFAN WOLTRAN
Affiliation:
TU Wien, Vienna, Austria
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Powerful formalisms for abstract argumentation have been proposed, among them abstract dialectical frameworks (ADFs) that allow for a succinct and flexible specification of the relationship between arguments and the GRAPPA framework which allows argumentation scenarios to be represented as arbitrary edge-labeled graphs. The complexity of ADFs and GRAPPA is located beyond NP and ranges up to the third level of the polynomial hierarchy. The combined complexity of Answer Set Programming (ASP) exactly matches this complexity when programs are restricted to predicates of bounded arity. In this paper, we exploit this coincidence and present novel efficient translations from ADFs and GRAPPA to ASP. More specifically, we provide reductions for the five main ADF semantics of admissible, complete, preferred, grounded, and stable interpretations, and exemplify how these reductions need to be adapted for GRAPPA for the admissible, complete, and preferred semantics.

Keywords

ADFsGRAPPAencodingsASP
Type
Original Article
Information
Theory and Practice of Logic Programming , Volume 20 , Issue 3 , May 2020 , pp. 391 - 431
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
Copyright © Cambridge University Press 2020

Footnotes

*

This research has been supported by DFG (projects BR 1817/7-2 as well as 389792660 – TRR 248) and FWF (projects I2854, Y698, P32830, S11409-N23, and W1255-N23). The authors also thank Jörg Pührer for his helpful observations regarding the encodings. Also thanks to Wolfgang Dvořák and Ringo Baumann for guiding the paper through the editing process.

References

Al-Abdulkarim, L., Atkinson, K. and Bench-Capon, T. 2016. A methodology for designing systems to reason with legal cases using abstract dialectical frameworks. Artif. Intell. Law 24, 1, 1–49.Google Scholar
Amgoud, L. and Prade, H. 2009. Using arguments for making and explaining decisions. Artif. Intell. 173, 3–4, 413–436.CrossRefGoogle Scholar
Atkinson, K. and Bench-Capon, T. J. M. 2018. Relating the ANGELIC methodology and ASPIC+. In Proc. COMMA. Frontiers in Artificial Intelligence and Applications, vol. 305. IOS Press, 109–116.Google Scholar
Bench-Capon, T. J. M. and Dunne, P. E. 2005. Argumentation in AI and Law: Editors’ Introduction. Artif. Intell. Law 13, 1, 1–8.Google Scholar
Berthold, M. 2016. Extending the DIAMOND system to work with GRAPPA. In Proc. SAFA, 52–62.Google Scholar
Bichler, M., Morak, M. and Woltran, S. 2016a. lpopt: A rule optimization tool for answer set programming. In LOPSTR. Lecture Notes in Computer Science, vol. 10184. Springer, 114–130.Google Scholar
Bichler, M., Morak, M. and Woltran, S. 2016b. The power of non-ground rules in answer set programming. TPLP 16, 5–6, 552–569.Google Scholar
Bichler, M., Morak, M. and Woltran, S. 2018. Single-shot epistemic logic program solving. In Proc. IJCAI. ijcai.org, 1714–1720.Google Scholar
Bogaerts, B., Janhunen, T. and Tasharrofi, S. 2016. Stable-unstable semantics: Beyond NP with normal logic programs. TPLP 16, 5–6, 570–586.Google Scholar
Booth, R. 2015. Judgment aggregation in abstract dialectical frameworks. In Advances in KR, Logic Programming, and Abstract Argumentation. Springer, 296–308.Google Scholar
Brewka, G., Diller, M., Heissenberger, G., Linsbichler, T. and Woltran, S. 2017. Solving advanced argumentation problems with answer-set programming. In Proc. AAAI. AAAI Press, 1077–1083.Google Scholar
Brewka, G., Eiter, T. and Truszczyński, M. 2011. Answer set programming at a glance. Commun. ACM 54, 12, 92–103.CrossRefGoogle Scholar
Brewka, G., Ellmauthaler, S., Strass, H., Wallner, J. P. and Woltran, S. 2018. Abstract Dialectical Frameworks: An Overview. In Handbook of Formal Argumentation, Baroni, P., Gabbay, D., Giacomin, M., and van der Torre, L., Eds. College Publications, Chapter 5, 236–286.Google Scholar
Brewka, G., Polberg, S. and Woltran, S. 2014. Generalizations of dung frameworks and their role in formal argumentation. IEEE Intell. Syst. 29, 1, 30–38.Google Scholar
Brewka, G., Pührer, J. and Woltran, S. 2019. Multi-valued GRAPPA. In Proc. JELIA. Lecture Notes in Computer Science, vol. 11468. Springer, 85–101.Google Scholar
Brewka, G., Strass, H., Ellmauthaler, S., Wallner, J. P. and Woltran, S. 2013. Abstract Dialectical Frameworks Revisited. In Proc. IJCAI. IJCAI/AAAI, 803–809.Google Scholar
Brewka, G., Strass, H., Wallner, J. P. and Woltran, S. 2018. Weighted abstract dialectical frameworks. In Proc. AAAI. AAAI Press, 1779–1786.Google Scholar
Brewka, G. and Woltran, S. 2010. Abstract Dialectical Frameworks. In Proc. KR. AAAI Press, 102–111.Google Scholar
Brewka, G. and Woltran, S. 2014. GRAPPA: A semantical framework for graph-based argument processing. In Proc. ECAI. Frontiers in Artificial Intelligence and Applications, vol. 263. IOS Press, 153–158.Google Scholar
Cabrio, E. and Villata, S. 2016. Abstract dialectical frameworks for text exploration. In Proc. ICAART’16. SciTePress, 85–95.Google Scholar
Cartwright, D. and Atkinson, K. 2009. Using computational argumentation to support E-participation. IEEE Intell. Syst. 24, 5, 42–52.CrossRefGoogle Scholar
Cerutti, F., Giacomin, M. and Vallati, M. 2017. Exploiting Planning Problems for Generating Challenging Abstract Argumentation Frameworks. URL: http://argumentationcompetition.org/2017/Planning2AF.pdf Google Scholar
Chandra, A. K. and Merlin, P. M. 1977. Optimal implementation of conjunctive queries in relational data bases. In Proc. STOC. ACM, 77–90.CrossRefGoogle Scholar
Charwat, G., Dvořák, W., Gaggl, S. A., Wallner, J. P. and Woltran, S. 2015. Methods for solving reasoning problems in abstract argumentation – A survey. Artif. Intell. 220, 28–63.CrossRefGoogle ScholarPubMed
Diller, M. 2017. Traffic Networks Become Argumentation Frameworks. URL: http://argumentationcompetition.org/2017/Traffic.pdf Google Scholar
Diller, M. 2019. Realising argumentation using answer set programming and quantified boolean formulas. Ph.D. thesis, TU Wien.Google Scholar
Diller, M., Keshavarzi Zafarghandi, A., Linsbichler, T. and Woltran, S. 2018. Investigating subclasses of abstract dialectical frameworks. In Proc. COMMA. Frontiers in Artificial Intelligence and Applications, vol. 305. IOS Press, 61–72.Google Scholar
Diller, M., Wallner, J. P. and Woltran, S. 2014. Reasoning in abstract dialectical frameworks using quantified boolean formulas. In Proc. COMMA. Frontiers in Artificial Intelligence and Applications, vol. 266. IOS Press, 241–252.Google Scholar
Diller, M., Wallner, J. P. and Woltran, S. 2015. Reasoning in Abstract Dialectical Frameworks Using Quantified Boolean Formulas. Argument & Computation 6, 2, 149–177.CrossRefGoogle Scholar
Dung, P. M. 1995. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-Person games. Artif. Intell. 77, 2, 321–358.CrossRefGoogle Scholar
Eén, N. and Sörensson, N. 2003. An extensible SAT-solver. In Proceedings of the 6th International Conference on Theory and Applications of Satisfiability Testing (SAT 2003), Giunchiglia, E. and Tacchella, A., Eds. Lecture Notes in Computer Science, vol. 2919. Springer, 502–518.Google Scholar
Eiter, T., Faber, W., Fink, M. and Woltran, S. 2007. Complexity results for answer set programming with bounded predicate arities and implications. Ann. Math. Artif. Intell. 51, 2–4, 123–165.CrossRefGoogle Scholar
Eiter, T. and Gottlob, G. 1995. On the computational cost of disjunctive logic programming: Propositional case. Ann. Math. Artif. Intell. 15, 3–4, 289–323.CrossRefGoogle Scholar
Eiter, T., Gottlob, G. and Mannila, H. 1997. Disjunctive datalog. ACM Trans. Database Syst. 22, 3, 364–418.CrossRefGoogle Scholar
Ellmauthaler, S. 2012. Abstract Dialectical Frameworks: Properties, Complexity, and Implementation. M.S. thesis, TU Wien.Google Scholar
Ellmauthaler, S. and Strass, H. 2014. The DIAMOND system for computing with abstract dialectical frameworks. In Proc. COMMA. Frontiers in Artificial Intelligence and Applications, vol. 266. IOS Press, 233–240.Google Scholar
Ellmauthaler, S. and Strass, H. 2016. DIAMOND 3.0 – A native C++ implementation of DIAMOND. In Proc. COMMA. Frontiers in Artificial Intelligence and Applications, vol. 287. IOS Press, 471–472.Google Scholar
Gaggl, S., Linsbichler, T., Maratea, M. and Woltran, S. 2018. Summary report of the second international competition on computational models of argumentation. AI Mag. 39, 77–79.CrossRefGoogle Scholar
Gaggl, S. A. and Strass, H. 2014. Decomposing abstract dialectical frameworks. In Proc. COMMA. Frontiers in Artificial Intelligence and Applications, vol. 266. IOS Press, 281–292.Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B., Lindauer, M., Ostrowski, M., Romero, J., Schaub, T. and Thiele, S. 2015. Potassco User Guide. URL: https://sourceforge.net/projects/potassco/files/guide/. [Accessed on November 22, 2016].Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B., Lühne, P., Obermeier, P., Ostrowski, M., Romero, J., Schaub, T., Schellhorn, S. and Wanko, P. 2018. The potsdam answer set solving collection 5.0. KI 32, 2–3, 181–182.Google Scholar
Gelfond, M. and Lifschitz, V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Comput. 9, 3/4, 365–386.CrossRefGoogle Scholar
Heule, M., Järvisalo, M., Lonsing, F., Seidl, M. and Biere, A. 2015. Clause elimination for SAT and QSAT. J. Artif. Intell. Res. 53, 127–168.CrossRefGoogle Scholar
Janhunen, T., Kaminski, R., Ostrowski, M., Schellhorn, S., Wanko, P. and Schaub, T. 2017. Clingo goes linear constraints over reals and integers. TPLP 17, 5–6, 872–888.Google Scholar
Janhunen, T. and Niemelä, I. 2016. The answer set programming paradigm. AI Magazine 37, 3, 13–24.CrossRefGoogle Scholar
Keshavarzi Zafarghandi, A. 2017. Investigating Subclasses of Abstract Dialectical Frameworks. M.S. thesis, Vienna University of Technology, Institute of Information Systems.Google Scholar
Lehtonen, T., Wallner, J. P. and Järvisalo, M. 2017. Assumption-Based Argumentation Translated to Argumentation Frameworks. URL: http://argumentationcompetition.org/2017/ABA2AF.pdf Google Scholar
Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S. and Scarcello, F. 2006. The DLV system for knowledge representation and reasoning. ACM Trans. Comput. Log. 7, 3, 499–562.CrossRefGoogle Scholar
Linsbichler, T., Maratea, M., Niskanen, A., Wallner, J. P. and Woltran, S. 2018. Novel algorithms for abstract dialectical frameworks based on complexity analysis of subclasses and SAT solving. In Proc. IJCAI. ijcai.org, 1905–1911.Google Scholar
Lonsing, F. and Biere, A. 2010. DepQBF: A Dependency-Aware QBF solver. JSAT 7, 2–3, 71–76.Google Scholar
Lonsing, F. and Egly, U. 2017. Depqbf 6.0: A search-based QBF solver beyond traditional QCDCL. In Proc. CADE. Lecture Notes in Computer Science, vol. 10395. Springer, 371–384.Google Scholar
McBurney, P., Parsons, S. and Rahwan, I., Eds. 2012. Proc. ArgMAS. Lecture Notes in Computer Science, vol. 7543. Springer.Google Scholar
Neugebauer, D. 2018. DABASCO: Generating AF, ADF, and ASPIC+ instances from real-world discussions. In Proc. COMMA. Frontiers in Artificial Intelligence and Applications, vol. 305. IOS Press, 469–470.Google Scholar
Polberg, S. 2014. Extension-based semantics of abstract dialectical frameworks. In Proc. STAIRS. Frontiers in Artificial Intelligence and Applications, vol. 264. IOS Press, 240–249.Google Scholar
Redl, C. 2017. Answer set programs with queries over subprograms. In Proc. LPNMR. Lecture Notes in Computer Science, vol. 10377. Springer, 160–175.Google Scholar
Strass, H. and Ellmauthaler, S. 2017. goDIAMOND 0.6.6 – ICCMA 2017 System Description. URL: http://argumentationcompetition.org/2017/goDIAMOND.pdf.Google Scholar
Strass, H. and Wallner, J. P. 2015. Analyzing the computational complexity of abstract dialectical frameworks via approximation fixpoint theory. Artif. Intell. 226, 34–74.CrossRefGoogle Scholar