Abstract
This paper presents a novel SAT-based approach for the computation of extensions in abstract argumentation, with focus on preferred semantics, and an empirical evaluation of its performances. The approach is based on the idea of reducing the problem of computing complete extensions to a SAT problem and then using a depth-first search method to derive preferred extensions. The proposed approach has been tested using two distinct SAT solvers and compared with three state-of-the-art systems for preferred extension computation. It turns out that the proposed approach delivers significantly better performances in the large majority of the considered cases.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Constraint Satisfaction Problem
- Conjunctive Normal Form
- Abstract Argumentation
- Argumentation Framework
- Complete Extension
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Amgoud, L., Devred, C.: Argumentation frameworks as constraint satisfaction problems. Annals of Mathematics and Artificial Intelligence, 1–18 (2013)
Ansótegui, C., Bonet, M.L., Levy, J.: SAT-based MaxSAT. Artificial Intelligence 196, 77–105 (2013)
Audemard, G., Simon, L.: Predicting learnt clauses quality in modern SAT solvers. In: Proceedings of IJCAI 2009, pp. 399–404 (2009)
Audemard, G., Simon, L.: Glucose 2.1 (2012), http://www.lri.fr/~simon/?page=glucose
Baroni, P., Caminada, M., Giacomin, M.: An introduction to argumentation semantics. Knowledge Engineering Review 26(4), 365–410 (2011)
Baroni, P., Giacomin, M.: Semantics of abstract argumentation systems. In: Argumentation in Artificial Intelligence, pp. 25–44. Springer (2009)
Baroni, P., Giacomin, M., Guida, G.: SCC-recursiveness: a general schema for argumentation semantics. Artificial Intelligence 168(1-2), 165–210 (2005)
Baroni, P., Cerutti, F., Dunne, P.E., Giacomin, M.: Automata for infinite argumentation structures. Artificial Intelligence 203, 104–150 (2013)
Besnard, P., Doutre, S.: Checking the acceptability of a set of arguments. In: Proceedings of NMR 2004, pp. 59–64 (2004)
Biere, A.: P{re,ic}oSAT@sc 2009. In: SAT Competition (2009)
Bistarelli, S., Santini, F.: Modeling and solving AFs with a constraint-based tool: Conarg. In: Modgil, S., Oren, N., Toni, F. (eds.) TAFA 2011. LNCS (LNAI), vol. 7132, pp. 99–116. Springer, Heidelberg (2012)
Caminada, M.: On the issue of reinstatement in argumentation. In: Fisher, M., van der Hoek, W., Konev, B., Lisitsa, A. (eds.) JELIA 2006. LNCS (LNAI), vol. 4160, pp. 111–123. Springer, Heidelberg (2006)
Caminada, M.: Semi-stable semantics. In: Proceedings of COMMA 2006, pp. 121–130 (2006)
Caminada, M., Gabbay, D.M.: A logical account of formal argumentation. Studia Logica (Special Issue: New Ideas in Argumentation Theory) 93(2-3), 109–145 (2009)
Cerutti, F., Dunne, P.E., Giacomin, M., Vallati, M.: Computing Preferred Extensions in Abstract Argumentation: a SAT-based Approach. Tech. rep. (2013), http://arxiv.org/abs/1310.4986
Dimopoulos, Y., Nebel, B., Toni, F.: Preferred arguments are harder to compute than stable extensions. In: Proceedings of IJCAI 1999, pp. 36–43 (1999)
Dimopoulos, Y., Torres, A.: Graph theoretical structures in logic programs and default theories. Journal Theoretical Computer Science 170, 209–244 (1996)
Doutre, S., Mengin, J.: Preferred extensions of argumentation frameworks: Query answering and computation. In: Goré, R., Leitsch, A., Nipkow, T. (eds.) IJCAR 2001. LNCS (LNAI), vol. 2083, pp. 272–288. Springer, Heidelberg (2001)
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–357 (1995)
Dung, P., Mancarella, P., Toni, F.: A dialectic procedure for sceptical, assumption-based argumentation. In: Proceedings of COMMA 2006, pp. 145–156 (2006)
Dunne, P.E., Wooldridge, M.: Complexity of abstract argumentation. In: Argumentation in Artificial Intelligence, pp. 85–104. Springer (2009)
Dvǒrák, W., Gaggl, S.A., Wallner, J., Woltran, S.: Making use of advances in answer-set programming for abstract argumentation systems. In: Proceedings of INAP 2011 (2011)
Dvǒrák, W., Järvisalo, M., Wallner, J.P., Woltran, S.: Complexity-sensitive decision procedures for abstract argumentation. In: Proceedings of KR 2012. AAAI Press (2012)
Egly, U., Gaggl, S.A., Woltran, S.: Aspartix: Implementing argumentation frameworks using answer-set programming. In: de la Garcia Banda, M., Pontelli, E. (eds.) ICLP 2008. LNCS, vol. 5366, pp. 734–738. Springer, Heidelberg (2008)
Jiménez, S., de la Rosa, T., Fernández, S., Fernández, F., Borrajo, D.: A review of machine learning for automated planning. Knowledge Engineering Review 27(4), 433–467 (2012)
Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S., Scarcello, F.: The DLV system for knowledge representation and reasoning. ACM Transactions on Computational Logic 7(3), 499–562 (2006)
Modgil, S., Caminada, M.: Proof theories and algorithms for abstract argumentation frameworks. In: Argumentation in Artificial Intelligence, pp. 105–129. Springer (2009)
Nofal, S., Dunne, P.E., Atkinson, K.: On preferred extension enumeration in abstract argumentation. In: Proceedings of COMMA 2012, pp. 205–216 (2012)
South, M., Vreeswijk, G., Fox, J.: Dungine: A Java Dung reasoner. In: Proceedings of COMMA 2008, pp. 360–368 (2008)
Wallner, J.P., Weissenbacher, G., Woltran, S.: Advanced SAT techniques for abstract argumentation. In: Leite, J., Son, T.C., Torroni, P., van der Torre, L., Woltran, S. (eds.) CLIMA XIV 2013. LNCS (LNAI), vol. 8143, pp. 138–154. Springer, Heidelberg (2013)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cerutti, F., Dunne, P.E., Giacomin, M., Vallati, M. (2014). Computing Preferred Extensions in Abstract Argumentation: A SAT-Based Approach. In: Black, E., Modgil, S., Oren, N. (eds) Theory and Applications of Formal Argumentation. TAFA 2013. Lecture Notes in Computer Science(), vol 8306. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-54373-9_12
Download citation
DOI: https://doi.org/10.1007/978-3-642-54373-9_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-54372-2
Online ISBN: 978-3-642-54373-9
eBook Packages: Computer ScienceComputer Science (R0)