More Web Proxy on the site http://driver.im/

research-article

On scaling the enumeration of the preferred extensions of abstract argumentation frameworks

Authors:

Gianvincenzo Alfano,

Francesco ParisiAuthors Info & Claims

SAC '19: Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing

Pages 1147 - 1153

https://doi.org/10.1145/3297280.3297393

Published: 08 April 2019 Publication History

Abstract

Argumentation has emerged as one of the major fields in Artificial Intelligence. In particular, Dung's abstract argumentation framework (AF) has received much attention in the last two decades, and many computational issues have been investigated for different argumentation semantics. Specifically, enumerating the sets of arguments (i.e., extensions) prescribed by an argumentation semantics is arguably one of the most challenging problems for AFs, and this is particularly the case for the well-known preferred semantics.

In this paper, we propose an algorithm for efficiently computing the set of preferred extensions of a given AF. Our technique relies on first computing the ideal extension for the given AF, and then using it to prune some arguments so that a smaller AF is obtained. Finally, we use state-of-the-art solvers for enumerating the preferred extensions of the pruned AF, and then return the extensions of the input AF after obtaining them from those of the pruned AF.

We experimentally compared our technique with the solver that won the track on enumerating preferred extensions of the last International Competition on Computational Models of Argumentation, and found that our approach is orders of magnitude faster than the computation from scratch.

References

[1]

Gianvincenzo Alfano, Sergio Greco, and Francesco Parisi. 2017. Computing Stable and Preferred Extensions of Dynamic Bipolar Argumentation Frameworks. In 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). 28--42.

[2]

Gianvincenzo Alfano, Sergio Greco, and Francesco Parisi. 2017. Efficient Computation of Extensions for Dynamic Abstract Argumentation Frameworks: An Incremental Approach. In Proceedings of International Conference on Artificial Intelligence (IJCAI). 49--55.

Digital Library

[3]

Gianvincenzo Alfano, Sergio Greco, and Francesco Parisi. 2018. Computing Extensions of Dynamic Abstract Argumentation Frameworks with Second-Order Attacks. In Proceedings of the 22nd International Database Engineering & Applications Symposium (IDEAS). 183--192.

Digital Library

[4]

Gianvincenzo Alfano, Sergio Greco, and Francesco Parisi. 2019. A Meta-Argumentation Approach for the Efficient Computation of Stable and Preferred Extensions in Dynamic Bipolar Argumentation Frameworks. Intelligenza Artificiale In press (2019).

[5]

Gianvincenzo Alfano, Sergio Greco, Francesco Parisi, Gerardo I. Simari, and Guillermo R. Simari. 2018. An Incremental Approach to Structured Argumentation over Dynamic Knowledge Bases. In Proceeding of the Sixteenth International Conference on Principles of Knowledge Representation and Reasoning (KR). 78--87.

[6]

Gianvincenzo Alfano, Sergio Greco, Francesco Parisi, Gerardo I. Simari, and Guillermo R. Simari. 2018. Incremental Computation of Warranted Arguments in Dynamic Defeasible Argumentation: The Rule Addition Case. In Proceedings of the 33rd Annual ACM Symposium on Applied Computing (SAC). 911--917.

Digital Library

[7]

Mario Alviano. 2017. The Pyglaf Argumentation Reasoner. In Proceedings of International Conference on Logic Programming (ICLP). 2:1--2:3.

[8]

Katie Atkinson, Pietro Baroni, Massimiliano Giacomin, Anthony Hunter, Henry Prakken, Chris Reed, Guillermo R. Simari, Matthias Thimm, and Serena Villata. 2017. Towards Artificial Argumentation. Artificial Intelligence Magazine 38, 3 (2017), 25--36.

Digital Library

[9]

Pietro Baroni, Martin Caminada, and Massimiliano Giacomin. 2011. An introduction to argumentation semantics. The Knowledge Engineering Review 26, 4 (2011), 365--410.

Digital Library

[10]

Pietro Baroni, Federico Cerutti, Massimiliano Giacomin, and Giovanni Guida. 2009. Encompassing Attacks to Attacks in Abstract Argumentation Frameworks. In Proc. of European Conf. on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU). 83--94.

Digital Library

[11]

Pietro Baroni, Massimiliano Giacomin, and Giovanni Guida. 2005. SCC-recursiveness: a general schema for argumentation semantics. Artificial Intelligence 168, 1--2 (2005), 162--210.

Digital Library

[12]

Pietro Baroni, Massimiliano Giacomin, and Beishui Liao. 2014. On topology-related properties of abstract argumentation semantics. A correction and extension to Dynamics of argumentation systems: A division-based method. Artificial Intelligence 212 (2014), 104--115.

Digital Library

[13]

Ringo Baumann. 2011. Splitting an Argumentation Framework. In Proceedings of International Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR). 40--53.

Digital Library

[14]

Ringo Baumann and Gerhard Brewka. 2010. Expanding Argumentation Frameworks: Enforcing and Monotonicity Results. In Proceedings of International Conference on Computational Models of Argument (COMMA). 75--86.

Digital Library

[15]

Trevor J. M. Bench-Capon and Paul E. Dunne. 2007. Argumentation in Artificial Intelligence. Artificial Intelligence 171, 10--15 (2007), 619--641.

Digital Library

[16]

Philippe Besnard and Anthony Hunter. 2008. Elements of Argumentation. MIT Press.

Digital Library

[17]

Richard Booth, Martin Caminada, and Braden Marshall. 2018. DISCO: A Web-Based Implementation of Discussion Games for Grounded and Preferred Semantics. In Proceedings of International Conference on Computational Models of Argument (COMMA). 453--454.

[18]

Martin W. A. Caminada, Wolfgang Dvorák, and Srdjan Vesic. 2016. Preferred semantics as socratic discussion. Journal of Logic and Computation 26, 4 (2016), 1257--1292.

[19]

Federico Cerutti, Massimiliano Giacomin, and Mauro Vallati. 2014. ArgSemSAT: Solving Argumentation Problems Using SAT. In Proceedings of International Conference on Computational Models of Argument (COMMA). 455--456.

[20]

Federico Cerutti, Massimiliano Giacomin, Mauro Vallati, and Marina Zanella. 2014. An SCC Recursive Meta-Algorithm for Computing Preferred Labellings in Abstract Argumentation. In Proceedings of International Conference on Principles of Knowledge Representation and Reasoning (KR).

Digital Library

[21]

Phan Minh Dung. 1995. On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games. Artificial Intelligence 77, 2 (1995), 321--358.

Digital Library

[22]

Phan Minh Dung, Paolo Mancarella, and Francesca Toni. 2007. Computing ideal sceptical argumentation. Artificial Intelligence 171, 10--15 (2007), 642--674.

Digital Library

[23]

Paul E. Dunne. 2009. The computational complexity of ideal semantics. Artificial Intelligence 173, 18 (2009), 1559--1591.

Digital Library

[24]

Paul E. Dunne and Michael Wooldridge. 2009. Complexity of Abstract Argumentation. In Argumentation in Artificial Intelligence. 85--104.

[25]

Wolfgang Dvorák, Reinhard Pichler, and Stefan Woltran. 2010. Towards Fixed-Parameter Tractable Algorithms for Argumentation. In Proceedings of International Conference on Principles of Knowledge Representation and Reasoning (KR).

Digital Library

[26]

Wolfgang Dvorák and Stefan Woltran. 2010. Complexity of semi-stable and stage semantics in argumentation frameworks. Inform. Process. Lett. 110, 11 (2010), 425--430.

Digital Library

[27]

Bettina Fazzinga, Sergio Flesca, and Francesco Parisi. 2015. On the Complexity of Probabilistic Abstract Argumentation Frameworks. ACM Trans. Comput. Log. 16, 3 (2015), 22.

Digital Library

[28]

Bettina Fazzinga, Sergio Flesca, and Francesco Parisi. 2016. On efficiently estimating the probability of extensions in abstract argumentation frameworks. Int. J. Approx. Reasoning 69 (2016), 106--132.

Digital Library

[29]

Alejandro J. García and Guillermo R. Simari. 2004. Defeasible Logic Programming: An Argumentative Approach. Theory and Practice of Logic Programming (TPLP) 4, 1--2 (2004), 95--138.

Digital Library

[30]

Sergio Greco and Francesco Parisi. 2016. Efficient Computation of Deterministic Extensions for Dynamic Abstract Argumentation Frameworks. In Proceedings of European Conference on Artificial Intelligence (ECAI). 1668--1669.

Digital Library

[31]

Sergio Greco and Francesco Parisi. 2016. Incremental Computation of Deterministic Extensions for Dynamic Argumentation Frameworks. In Proceedings of European Conference on Logics in Artificial Intelligence (JELIA). 288--304.

[32]

David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. 1988. On Generating All Maximal Independent Sets. Inform. Process. Lett. 27, 3 (1988), 119--123.

Digital Library

[33]

Markus Kröll, Reinhard Pichler, and Stefan Woltran. 2017. On the Complexity of Enumerating the Extensions of Abstract Argumentation Frameworks. In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI). 1145--1152.

Digital Library

[34]

Jean-Marie Lagniez, Emmanuel Lonca, and Jean-Guy Mailly. 2015. CoQuiAAS: A Constraint-Based Quick Abstract Argumentation Solver. In Proceeding of IEEE International Conference on Tools with Artificial Intelligence (ICTAI). 928--935.

Digital Library

[35]

Beishui Liao. 2013. Toward incremental computation of argumentation semantics: A decomposition-based approach. Annals of Mathematics and Artificial Intelligence 67, 3--4 (2013), 319--358.

Digital Library

[36]

Beishui Liao and Huaxin Huang. 2013. Partial semantics of argumentation: basic properties and empirical results. Journal of Logic and Computation 23, 3 (2013), 541--562.

Digital Library

[37]

Beishui Liao, Liyun Lei, and Jianhua Dai. 2013. Computing Preferred Labellings by Exploiting SCCs and Most Sceptically Rejected Arguments. In Theory and Applications of Formal Argumentation - Second International Workshop, TAFA 2013, Beijing, China, August 3--5, 2013, Revised Selected papers. 194--208.

[38]

Bei Shui Liao, Li Jin, and Robert C. Koons. 2011. Dynamics of argumentation systems: A division-based method. Artificial Intelligence 175, 11 (2011), 1790--1814.

Digital Library

[39]

Sanjay Modgil. 2009. Reasoning about preferences in argumentation frameworks. Artificial Intelligence 173, 9--10 (2009), 901--934.

Digital Library

[40]

Sanjay Modgil and Henry Prakken. 2011. Revisiting Preferences and Argumentation. In Proceedings of International Conference on Artificial Intelligence (IJCAI). 1021--1026.

Digital Library

[41]

Sanjay Modgil, Francesca Toni, Floris Bex, Ivan Bratko, Carlos I. Chesñevar, Wolfgang Dvŏrák, Marcelo A. Falappa, Xiuyi Fan, Sarah Alice Gaggl, Alejandro J. García, Maria P. González, Thomas F. Gordon, João Leite, Martin Mozina, Chris Reed, Guillermo R. Simari, Stefan Szeider, Paolo Torroni, and Stefan Woltran. 2013. Agreement Technologies. Law, Governance and Technology, Vol. 8. Springer, New York, Chapter 21: The Added Value of Argumentation: Examples and Challenges, 357--404.

[42]

Emilia Oikarinen and Stefan Woltran. 2011. Characterizing strong equivalence for argumentation frameworks. Artificial Intelligence 175, 14--15 (2011), 1985--2009.

Digital Library

[43]

Iyad Rahwan and Guillermo R. Simari. 2009. Argumentation in Artificial Intelligence (1st ed.). Springer Publishing Company, Incorporated.

Digital Library

[44]

Serena Villata, Guido Boella, Dov M. Gabbay, and Leendert W. N. van der Torre. 2012. Modelling defeasible and prioritized support in bipolar argumentation. Annals of Mathematics and Artificial Intelligence 66, 1--4 (2012), 163--197.

Digital Library

Cited By

Rodrigues OHong JLanperne MPark JCerny TShahriar H(2023)Representing and Manipulating Large Sequences of Argumentation LabellingsProceedings of the 38th ACM/SIGAPP Symposium on Applied Computing10.1145/3555776.3577756(995-1002)Online publication date: 27-Mar-2023
https://dl.acm.org/doi/10.1145/3555776.3577756
Alfano GGreco SParisi F(2019)An efficient algorithm for skeptical preferred acceptance in dynamic argumentation frameworksProceedings of the 28th International Joint Conference on Artificial Intelligence10.5555/3367032.3367036(18-24)Online publication date: 10-Aug-2019
https://dl.acm.org/doi/10.5555/3367032.3367036
Alfano G(2019)An Efficient Algorithm for Computing the Set of Semi-stable ExtensionsFlexible Query Answering Systems10.1007/978-3-030-27629-4_15(139-151)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1007/978-3-030-27629-4_15

Index Terms

On scaling the enumeration of the preferred extensions of abstract argumentation frameworks
1. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning

Recommendations

Determining Preferences over Extensions: A Cautious Approach to Preference-Based Argumentation Frameworks
Symbolic and Quantitative Approaches to Reasoning with Uncertainty
Abstract
Preferences in abstract argumentation frameworks allow to represent the comparative strength of arguments, or preferences between values that arguments promote. In this paper, we reconsider the approach by Amgoud and Vesic, which computes the ...
On the responsibility for undecisiveness in preferred and stable labellings in abstract argumentation
Abstract
Different semantics of abstract Argumentation Frameworks (AFs) provide different levels of decisiveness for reasoning about the acceptability of conflicting arguments. The stable semantics is useful for applications requiring a high ...
New stochastic local search approaches for computing preferred extensions of abstract argumentation

Several efficient SAT-based methods for computing the preferred extensions in (abstract) argumentation frameworks (AF) are proposed lately. However, only complete SAT solvers have been exploited so far. It is a natural question that how the appealing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SAC '19: Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing

April 2019

2682 pages

ISBN:9781450359337

DOI:10.1145/3297280

Conference Chairs:
Chih-Cheng Hung
Kennesaw State University, Marietta, Georgia
,
George A. Papadopoulos
University of Cyprus, Nicosia, Cyprus

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 April 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Best Paper

Author Tags

Qualifiers

Research-article

Conference

SAC '19

Sponsor:

SIGAPP

SAC '19: The 34th ACM/SIGAPP Symposium on Applied Computing

April 8 - 12, 2019

Limassol, Cyprus

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Upcoming Conference

SAC '25

Sponsor:
sigapp

The 40th ACM/SIGAPP Symposium on Applied Computing

March 31 - April 4, 2025

Catania , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
112
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Rodrigues OHong JLanperne MPark JCerny TShahriar H(2023)Representing and Manipulating Large Sequences of Argumentation LabellingsProceedings of the 38th ACM/SIGAPP Symposium on Applied Computing10.1145/3555776.3577756(995-1002)Online publication date: 27-Mar-2023
https://dl.acm.org/doi/10.1145/3555776.3577756
Alfano GGreco SParisi F(2019)An efficient algorithm for skeptical preferred acceptance in dynamic argumentation frameworksProceedings of the 28th International Joint Conference on Artificial Intelligence10.5555/3367032.3367036(18-24)Online publication date: 10-Aug-2019
https://dl.acm.org/doi/10.5555/3367032.3367036
Alfano G(2019)An Efficient Algorithm for Computing the Set of Semi-stable ExtensionsFlexible Query Answering Systems10.1007/978-3-030-27629-4_15(139-151)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1007/978-3-030-27629-4_15

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents