Argumentation Reasoning via Circumscription with Pyglaf

• Autorzy: Alviano Mario

Identyfikatory

DOI

10.3233/FI-2019-1808

• Języki publikacji: EN

Abstrakty

EN

The fundamental mechanism that humans use in argumentation can be formalized in abstract argumentation frameworks. Many semantics are associated with abstract argumentation frameworks, each one consisting of a set of extensions, that is, a set of sets of arguments. Some of these semantics are based on preference relations that essentially impose to maximize or minimize some property. This paper presents the argumentation reasoner PYGLAF, which provides a uniform view of many semantics for abstract argumentation frameworks in terms of circumscription. Specifically, several computational problems of abstract argumentation frameworks are reduced to circumscription by means of linear encodings, and a few others are solved by means of a sequence of calls to an oracle for circumscription. Finally, grounded extensions are obtained in polynomial time by unit propagation, and acceptance problems are addressed by first checking cardinality optimal models of circumscribed theories, so that the naive extension enumeration is possibly avoided.

Słowa kluczowe

EN

abstract argumentation frameworks; incremental solving; minimal model enumeration; propositional circumscription

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 167, nr 1-2
• Strony: 1--30
• Opis fizyczny: Bibliogr. 42 poz., rys., tab., wykr.

Twórcy

autor

Alviano Mario

• Department of Mathematics and Computer Science, University of Calabria, via Pietro Bucci 30B, 87036 Rende (CS), Italy

Bibliografia

• [1] Dung PM. On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games. Artif. Intell., 1995. 77(2):321-358. doi:10.1016/0004-3702(94)00041-X. URL http://dx.doi.org/10.1016/0004-3702(94)00041-X.
• [2] Caminada MWA, Carnielli WA, Dunne PE. Semi-stable semantics. J. Log. Comput., 2012. 22(5):1207-1254. doi:10.1093/logcom/exr033. URL http://dx.doi.org/10.1093/logcom/exr033.
• [3] Dung PM, Mancarella P, Toni F. Computing ideal sceptical argumentation. Artif. Intell., 2007. 171(10-15):642-674. doi:10.1016/j.artint.2007.05.003. URL http://dx.doi.org/10.1016/j.artint.2007.05.003.
• [4] Verheij B. Two Approaches to Dialectical Argumentation: Admissible Sets and Argumentation Stages. In: In Proceedings of the biannual International Conference on Formal and Applied Practical Reasoning (FAPR) workshop. Universiteit, 1996 pp. 357-368.
• [5] McCarthy J. Circumscription - A Form of Non-Monotonic Reasoning. Artif. Intell., 1980. 13(1-2):27-39. doi:10.1016/0004-3702(80)90011-9. URL http://dx.doi.org/10.1016/0004-3702(80)90011-9.
• [6] Lifschitz V. On the Satisfiability of Circumscription. Artif. Intell., 1986. 28(1):17-27. doi:10.1016/0004-3702(86)90028-7. URL http://dx.doi.org/10.1016/0004-3702(86)90028-7.
• [7] Alviano M. Ingredients of the Argumentation Reasoner pyglaf: Python, Circumscription, and Glucose to Taste. In: Maratea M, Serina I (eds.), Proceedings of the 24th RCRA International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion 2017 colocated with the 16th International Conference of the Italian Association for Artificial Intelligence (AI*IA 2017), Bari, Italy, November 14-15, 2017., volume 2011 of CEUR Workshop Proceedings. CEUR-WS.org, 2017 pp. 1-16. URL http://ceur-ws.org/Vol-2011/paper1.pdf.
• [8] Alviano M. Model enumeration in propositional circumscription via unsatisfiable core analysis. TPLP, 2017. 17:1-18. doi:10.1017/S1471068417000278.
• [9] Audemard G, Simon L. Predicting Learnt Clauses Quality in Modern SAT Solvers. In: Boutilier C (ed.), IJCAI 2009, Pasadena, California, USA, July 11-17, 2009. 2009 pp. 399-404. URL http://ijcai.org/Proceedings/09/Papers/074.pdf.
• [10] Alviano M, Dodaro C, Ricca F. A MaxSAT Algorithm Using Cardinality Constraints of Bounded Size. In: Yang Q, Wooldridge M (eds.), IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015. AAAI Press, 2015 pp. 2677-2683.
• [11] Alviano M, Dodaro C. Anytime answer set optimization via unsatisfiable core shrinking. TPLP, 2016. 16(5-6):533-551. doi:10.1017/S147106841600020X.
• [12] Alviano M, Dodaro C. Unsatisfiable Core Shrinking for Anytime Answer Set Optimization. In: Sierra C (ed.), IJCAI 2017, Melbourne, Australia, August 19-25, 2017. ijcai.org, 2017 pp. 4781-4785. doi:10.24963/ijcai.2017/666.
• [13] Alviano M, Dodaro C, Faber W, Leone N, Ricca F. WASP: A Native ASP Solver Based on Constraint Learning. In: Cabalar P, Son TC (eds.), LPNMR 2013, Corunna, Spain, September 15-19, 2013. Proceedings, volume 8148 of LNCS. Springer, 2013 pp. 54-66. doi:10.1007/978-3-642-40564-8_6.
• [14] Alviano M, Dodaro C, Leone N, Ricca F. Advances in WASP. In: Calimeri F, Ianni G, Truszczynski M (eds.), Logic Programming and Nonmonotonic Reasoning - 13th International Conference, LPNMR 2015, Lexington, KY, USA, September 27-30, 2015. Proceedings, volume 9345 of LNCS. Springer, 2015 pp. 40-54. doi:10.1007/978-3-319-23264-5_5.
• [15] Dodaro C, Alviano M, Faber W, Leone N, Ricca F, Sirianni M. The Birth of a WASP: Preliminary Report on a New ASP Solver. In: Fioravanti F (ed.), Proceedings of the 26th Italian Conference on Computational Logic, Pescara, Italy, August 31 - September 2, 2011, volume 810 of CEUR Workshop Proceedings. CEUR-WS.org, 2011 pp. 99-113. URL http://ceur-ws.org/Vol-810/paper-l06.pdf.
• [16] Alviano M, Dodaro C. Answer Set Enumeration via Assumption Literals. In: Adorni G, Cagnoni S, Gori M, Maratea M (eds.), AI*IA 2016, Genova, Italy, November 29 - December 1, 2016, Proceedings, volume 10037 of LNCS. Springer, 2016 pp. 149-163. doi:10.1007/978-3-319-49130-1_12. URL https://doi.org/10.1007/978-3-319-49130-1_12.
• [17] Charwat G, Dvorák W, Gaggl SA, Wallner JP, Woltran S. Methods for solving reasoning problems in abstract argumentation - A survey. Artif. Intell., 2015. 220:28-63. doi:10.1016/j.artint.2014.11.008. URL http://dx.doi.org/10.1016/j.artint.2014.11.008.
• [18] Caminada M. A labelling approach for ideal and stage semantics. Argument & Computation, 2011. 2(1):1-21. doi:10.1080/19462166.2010.515036.
• [19] Cerutti F, Giacomin M, Vallati M. ArgSemSAT: Solving Argumentation Problems Using SAT. In: Parsons S, Oren N, Reed C, Cerutti F (eds.), Computational Models of Argument - Proceedings of COMMA 2014, Atholl Palace Hotel, Scottish Highlands, UK, September 9-12, 2014, volume 266 of Frontiers in Artificial Intelligence and Applications. IOS Press, 2014 pp. 455-456. doi:10.3233/978-1-61499-436-7-455. URL http://dx.doi.org/10.3233/978-1-61499-436-7-455.
• [20] Beierle C, Brons F, Potyka N. A Software System Using a SAT Solver for Reasoning Under Complete, Stable, Preferred, and Grounded Argumentation Semantics. In: Hölldobler S, Krötzsch M, Peñaloza R, Rudolph S (eds.), KI 2015: Advances in Artificial Intelligence - 38th Annual German Conference on AI, Dresden, Germany, September 21-25, 2015, Proceedings, volume 9324 of LNCS. Springer, 2015 pp. 241-248. doi:10.1007/978-3-319-24489-1_19. URL http://dx.doi.org/10.1007/978-3-319-24489-1_19.
• [21] Caminada M. On the Issue of Reinstatement in Argumentation. In: Fisher M, van der Hoek W, Konev B, Lisitsa A (eds.), Logics in Artificial Intelligence, 10th European Conference, JELIA 2006, Liverpool, UK, September 13-15, 2006, Proceedings, volume 4160 of LNCS. Springer, 2006 pp. 111-123. doi:10.1007/11853886_11.
• [22] Caminada MWA, Gabbay DM. A Logical Account of Formal Argumentation. Studia Logica, 2009. 93(2-3):109-145. doi:10.1007/s11225-009-9218-x. URL http://dx.doi.org/10.1007/s11225-009-9218-x.
• [23] Gaggl SA, Manthey N, Ronca A, Wallner JP, Woltran S. Improved answer-set programming encodings for abstract argumentation. TPLP, 2015. 15(4-5):434-448. doi:10.1017/S1471068415000149. URL http://dx.doi.org/10.1017/S1471068415000149.
• [24] Bistarelli S, Santini F. ConArg: Argumentation with Constraints. In: Ossowski S, Toni F, Vouros GA (eds.), Proceedings of the First International Conference on Agreement Technologies, AT 2012, Dubrovnik, Croatia, October 15-16, 2012, volume 918 of CEUR Workshop Proceedings. CEUR-WS.org, 2012 pp. 197-198.
• [25] Bistarelli S, Rossi F, Santini F. Enumerating Extensions on Random Abstract-AFs with ArgTools, Aspartix, ConArg2, and Dung-O-Matic. In: Bulling N, van der Torre LWN, Villata S, Jamroga W, Vasconcelos WW (eds.), Computational Logic in Multi-Agent Systems - 15th International Workshop, CLIMA XV, Prague, Czech Republic, August 18-19, 2014. Proceedings, volume 8624 of LNCS. Springer, 2014 pp. 70-86. doi:10.1007/978-3-319-09764-0_5. URL http://dx.doi.org/10.1007/978-3-319-09764-0_5.
• [26] Bistarelli S, Rossi F, Santini F. ConArg: A Tool for Classical and Weighted Argumentation. In: Baroni P, Gordon TF, Scheffler T, Stede M (eds.), Computational Models of Argument - Proceedings of COMMA 2016, Potsdam, Germany, 12-16 September, 2016., volume 287 of Frontiers in Artificial Intelligence and Applications. IOS Press, 2016 pp. 463-464. doi:10.3233/978-1-61499-686-6-463.
• [27] Bistarelli S, Rossi F, Santini F. A ConArg-based Library for Abstract Argumentation. In: Bistarelli S, Giacomin M, Pazienza A (eds.), Proceedings of the 1st Workshop on Advances In Argumentation In Artificial Intelligence co-located with XVI International Conference of the Italian Association for Artificial Intelligence (AI*IA 2017), Bari, Italy, November 16-17, 2017., volume 2012 of CEUR Workshop Proceedings. CEUR-WS.org, 2017 pp. 7-21. URL http://ceur-ws.org/Vol-2012/AI3-2017\_paper\_2.pdf.
• [28] Bistarelli S, Rossi F, Santini F. A ConArg-Based Library for Abstract Argumentation. In: 29th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2017, Boston, MA, USA, November 6-8, 2017. IEEE Computer Society, 2017 pp. 374-381. doi:10.1109/ICTAI.2017.00065. URL https://doi.org/10.1109/ICTAI.2017.00065.
• [29] Cerutti F, Dunne PE, Giacomin M, Vallati M. Computing Preferred Extensions in Abstract Argumentation: A SAT-Based Approach. In: Black E, Modgil S, Oren N (eds.), Theory and Applications of Formal Argumentation - Second International Workshop, TAFA 2013, Beijing, China, August 3-5, 2013, Revised Selected papers, volume 8306 of LNCS. Springer, 2013 pp. 176-193. doi:10.1007/978-3-642-54373-9_12. URL http://dx.doi.org/10.1007/978-3-642-54373-9_12.
• [30] Faber W, Vallati M, Cerutti F, Giacomin M. Solving Set Optimization Problems by Cardinality Optimization with an Application to Argumentation. In: Kaminka GA, Fox M, Bouquet P, Hüllermeier E, Dignum V, Dignum F, van Harmelen F (eds.), ECAI 2016 - 22nd European Conference on Artificial Intelligence, 29 August-2 September 2016, The Hague, The Netherlands - Including Prestigious Applications of Artificial Intelligence (PAIS 2016), volume 285 of Frontiers in Artificial Intelligence and Applications. IOS Press, 2016 pp. 966-973. doi:10.3233/978-1-61499-672-9-966. URL http://dx.doi.org/10.3233/978-1-61499-672-9-966.
• [31] Lagniez J, Lonca E, Mailly J. CoQuiAAS: A Constraint-Based Quick Abstract Argumentation Solver. In: 27th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2015, Vietri sul Mare, Italy, November 9-11, 2015. IEEE Computer Society, 2015 pp. 928-935. doi:10.1109/ICTAI.2015.134. URL https://doi.org/10.1109/ICTAI.2015.134.
• [32] Pu F, Luo G, Jiang Z. Encoding Argumentation Semantics by Boolean Algebra. IEICE Transactions, 2017. 100-D(4):838-848. URL http://search.ieice.org/bin/summary.php?id=e100-d_4_838.
• [33] Dvorák W, Järvisalo M, Wallner JP, Woltran S. Complexity-sensitive decision procedures for abstract argumentation. Artif. Intell., 2014. 206:53-78. doi:10.1016/j.artint.2013.10.001. URL https://doi.org/10.1016/j.artint.2013.10.001.
• [34] Besnard P, Doutre S. Checking the acceptability of a set of arguments. In: Delgrande JP, Schaub T (eds.), 10th International Workshop on Non-Monotonic Reasoning (NMR 2004), Whistler, Canada, June 6-8, 2004, Proceedings. 2004 pp. 59-64. URL http://www.pims.math.ca/science/2004/NMR/papers.html.
• [35] Wallner JP, Weissenbacher G, Woltran S. Advanced SAT Techniques for Abstract Argumentation. In: Leite J, Son TC, Torroni P, van der Torre L, Woltran S (eds.), Computational Logic in Multi-Agent Systems - 14th International Workshop, CLIMA XIV, Corunna, Spain, September 16-18, 2013. Proceedings, volume 8143 of LNCS. Springer, 2013 pp. 138-154. doi:10.1007/978-3-642-40624-9_9. URL http://dx.doi.org/10.1007/978-3-642-40624-9_9.
• [36] Alviano M, Dodaro C, Ricca F. Anytime Computation of Cautious Consequences in Answer Set Programming. TPLP, 2014. 14(4-5):755-770. doi:10.1017/S1471068414000325. URL https://doi.org/10.1017/S1471068414000325.
• [37] Alviano M, Dodaro C, Järvisalo M, Maratea M, Previti A. Cautious reasoning in ASP via minimal models and unsatisfiable cores. TPLP, 2018. 18(3-4):319-336. doi:10.1017/S1471068418000145. URL https://doi.org/10.1017/S1471068418000145.
• [38] Romero J, Schaub T, Wanko P. Computing Diverse Optimal Stable Models. In: Carro M, King A, Saeedloei N, Vos MD (eds.), ICLP 2016 TCs, October 16-21, 2016, New York City, USA, volume 52 of OASICS. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016 pp. 3:1-3:14. doi:10.4230/OASIcs.ICLP.2016.3. URL https://doi.org/10.4230/OASIcs.ICLP.2016.3.
• [39] Alviano M, Romero J, Schaub T. Preference Relations by Approximation. In: Thielscher M, Toni F, Wolter F (eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the Sixteenth International Conference, KR 2018, Tempe, Arizona, 30 October - 2 November 2018. AAAI Press, 2018 pp. 2-11. URL https://aaai.org/ocs/index.php/KR/KR18/paper/view/18001.
• [40] Oikarinen E, Janhunen T. circ2dlp - Translating Circumscription into Disjunctive Logic Programming. In: Baral C, Greco G, Leone N, Terracina G (eds.), LPNMR 2005, Diamante, Italy, September 5-8, 2005, volume 3662 of LNCS. Springer, 2005 pp. 405-409. doi:10.1007/11546207_36. URL https://doi.org/10.1007/11546207_36.
• [41] Egly U, Gaggl SA, Woltran S. Answer-set programming encodings for argumentation frameworks. Argument & Computation, 2010. 1(2):147-177. doi:10.1080/19462166.2010.486479. URL https://doi.org/10.1080/19462166.2010.486479.
• [42] Alviano M. Query Answering in Propositional Circumscription. In: Lang J (ed.), Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden. ijcai.org, 2018 pp. 1669-1675. doi:10.24963/ijcai.2018/231. URL https://doi.org/10.24963/ijcai.2018/231.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).