{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,24]],"date-time":"2026-04-24T04:07:22Z","timestamp":1777003642356,"version":"3.51.4"},"reference-count":47,"publisher":"Oxford University Press (OUP)","issue":"2","license":[{"start":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T00:00:00Z","timestamp":1674604800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,3,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Incomplete Argumentation Frameworks (IAFs) have been defined to incorporate some qualitative uncertainty in abstract argumentation: information such as \u2018I am not sure whether this argument exists\u2019 or \u2018I am not sure whether this argument attacks that one\u2019 can be expressed. Reasoning with IAFs is classically based on a set of completions, i.e. standard argumentation frameworks (AFs) that represent the possible worlds encoded in the IAF. The number of these completions may be exponential with respect to the number of arguments in the IAF. This leads, in some cases, to an increase of the complexity of reasoning, compared to the complexity of standard AFs. In this paper, we follow an approach that was initiated for Partial Argumentation Frameworks (PAFs) (a subclass of IAFs), which consists in defining new forms of conflict-freeness and defense, the properties that underly the definition of Dung\u2019s semantics for AFs. We generalize these semantics from PAFs to IAFs. We show that, among three possible types of admissibility, only two of them satisfy some desirable properties. We use them to define two new families of extension-based semantics. We study the properties of these semantics, and in particular, we show that their complexity remains the same as in the case of Dung\u2019s AFs. Finally, we propose a logical encoding of these semantics, and we show experimentally that this encoding can be used efficiently to reason with IAFs, thanks to the power of modern SAT solvers.<\/jats:p>","DOI":"10.1093\/logcom\/exac099","type":"journal-article","created":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T00:45:22Z","timestamp":1674780322000},"page":"406-435","source":"Crossref","is-referenced-by-count":5,"title":["Extension-based semantics for incomplete argumentation frameworks: properties, complexity and algorithms"],"prefix":"10.1093","volume":"33","author":[{"given":"Jean-Guy","family":"Mailly","sequence":"first","affiliation":[{"name":"Universit\u00e9 Paris Cit\u00e9 , LIPADE, F-75006 Paris, France"}]}],"member":"286","published-online":{"date-parts":[[2023,1,25]]},"reference":[{"key":"2023030410205131400_","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1103\/RevModPhys.74.47","article-title":"Statistical mechanics of complex networks","volume":"74","author":"Albert","year":"2002","journal-title":"Reviews of Modern Physics"},{"key":"2023030410205131400_","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1023\/A:1014490210693","article-title":"A reasoning model based on the production of acceptable arguments","volume":"34","author":"Amgoud","year":"2002","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"2023030410205131400_","doi-asserted-by":"crossref","first-page":"1062","DOI":"10.1002\/int.20307","article-title":"On bipolarity in argumentation frameworks","volume":"23","author":"Amgoud","year":"2008","journal-title":"International Journal of Intelligent Systems"},{"key":"2023030410205131400_","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity\u2014A Modern Approach","author":"Arora","year":"2009"},{"key":"2023030410205131400_","first-page":"159","article-title":"Abstract argumentation frameworks and their semantics","volume-title":"Handbook of Formal Argumentation","author":"Baroni","year":"2018"},{"key":"2023030410205131400_","article-title":"Encompassing uncertainty in argumentation schemes","volume-title":"Proceedings of the Workshop on Frontiers and Connections between Argumentation Theory and Natural Language Processing, Forl\u00ec-Cesena, Italy, July 21\u201325, 2014","author":"Baroni","year":"2014"},{"key":"2023030410205131400_","doi-asserted-by":"crossref","DOI":"10.1016\/j.artint.2021.103470","article-title":"Acceptance in incomplete argumentation frameworks","volume":"295","author":"Baumeister","year":"2021","journal-title":"Artificial Intelligence"},{"key":"2023030410205131400_","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/978-3-319-23114-3_21","article-title":"Verification in attack-incomplete argumentation frameworks","volume-title":"4th International Conference on Algorithmic Decision Theory (ADT 2015)","author":"Baumeister","year":"2015"},{"key":"2023030410205131400_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.artint.2018.08.001","article-title":"Verification in incomplete argumentation frameworks","volume":"264","author":"Baumeister","year":"2018","journal-title":"Artificial Intelligence"},{"key":"2023030410205131400_","first-page":"443","article-title":"Value-based argumentation frameworks","volume-title":"9th International Workshop on Non-Monotonic Reasoning (NMR 2002), April 19\u201321, Toulouse, France, Proceedings","author":"Bench-Capon"},{"key":"2023030410205131400_","first-page":"59","article-title":"Checking the acceptability of a set of arguments","volume-title":"10th International Workshop on Non-Monotonic Reasoning (NMR 2004)","author":"Besnard","year":"2004"},{"key":"2023030410205131400_","article-title":"Frontiers in Artificial Intelligence and Applications","volume-title":"Handbook of Satisfiability","author":"Biere","year":"2009"},{"key":"2023030410205131400_","doi-asserted-by":"crossref","first-page":"277","DOI":"10.3233\/AAC-190463","article-title":"Strong admissibility revisited: theory and applications","volume":"10","author":"Caminada","year":"2019","journal-title":"Argument & Computation"},{"key":"2023030410205131400_","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/978-3-540-75256-1_25","article-title":"Handling ignorance in argumentation: Semantics of partial argumentation frameworks","volume-title":"9th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU 2007)","author":"Cayrol","year":"2007"},{"key":"2023030410205131400_","first-page":"151","article-title":"The complexity of theorem-proving procedures","volume-title":"Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, May 3\u20135, 1971, Shaker Heights, Ohio, USA","author":"Cook"},{"key":"2023030410205131400_","doi-asserted-by":"crossref","first-page":"730","DOI":"10.1016\/j.artint.2007.04.012","article-title":"On the merging of Dung\u2019s argumentation systems","volume":"171","author":"Coste-Marquis","year":"2007","journal-title":"Artificial Intelligence"},{"key":"2023030410205131400_","first-page":"4678","article-title":"Control argumentation frameworks","volume-title":"32nd AAAI Conference on Artificial Intelligence (AAAI 2018)","author":"Dimopoulos","year":"2018"},{"key":"2023030410205131400_","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/0004-3702(94)00041-X","article-title":"On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games","volume":"77","author":"Dung","year":"1995","journal-title":"Artificial Intelligence"},{"key":"2023030410205131400_","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1016\/j.artint.2010.09.005","article-title":"Weighted argument systems: basic definitions, algorithms, and complexity results","volume":"175","author":"Dunne","year":"2011","journal-title":"Artificial Intelligence"},{"key":"2023030410205131400_","first-page":"631","article-title":"Computational problems in formal argumentation and their complexity","volume-title":"Handbook of Formal Argumentation","author":"Dvor\u00e1k","year":"2018"},{"key":"2023030410205131400_","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.artint.2013.10.001","article-title":"Complexity-sensitive decision procedures for abstract argumentation","volume":"206","author":"Dvor\u00e1k","year":"2014","journal-title":"Artificial Intelligence"},{"key":"2023030410205131400_","first-page":"133","article-title":"Reasoning in argumentation frameworks using quantified boolean formulas","volume-title":"Computational Models of Argument: Proceedings of COMMA 2006, September 11\u201312, 2006, Liverpool, UK","author":"Egly","year":"2006"},{"key":"2023030410205131400_","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","article-title":"On random graphs. I","volume":"6","author":"Erd\u00f6s","year":"1959","journal-title":"Publicationes Mathematicae"},{"key":"2023030410205131400_","first-page":"1712","article-title":"Revisiting the notion of extension over incomplete abstract argumentation frameworks","volume-title":"29th International Joint Conference on Artificial Intelligence (IJCAI 2020)","author":"Fazzinga","year":"2020"},{"key":"2023030410205131400_","first-page":"189","article-title":"Reasoning over argument-incomplete aafs in the presence of correlations","volume-title":"Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event \/ Montreal, Canada, 19\u201327 August 2021","author":"Fazzinga","year":"2021"},{"key":"2023030410205131400_","first-page":"301","article-title":"Reasoning over attack-incomplete aafs in the presence of correlations","volume-title":"Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021, Online event, November 3\u201312, 2021","author":"Fazzinga","year":"2021"},{"key":"2023030410205131400_","doi-asserted-by":"crossref","first-page":"103193","DOI":"10.1016\/j.artint.2019.103193","article-title":"Design and results of the second international competition on computational models of argumentation","volume":"279","author":"Gaggl","year":"2020","journal-title":"Artificial Intelligence"},{"key":"2023030410205131400_","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1016\/j.artint.2019.05.001","article-title":"On the graded acceptability of arguments in abstract and instantiated argumentation","volume":"275","author":"Grossi","year":"2019","journal-title":"Artificial Intelligence"},{"key":"2023030410205131400_","first-page":"190","article-title":"Abstract argumentation with qualitative uncertainty: An analysis in dynamic logic","volume-title":"Logic and Argumentation\u20144th International Conference, CLAR 2021, Hangzhou, China, October 20\u201322, 2021, Proceedings","author":"Herzig","year":"2021"},{"key":"2023030410205131400_","first-page":"117","article-title":"Some foundations for probabilistic abstract argumentation","volume-title":"Computational Models of Argument\u2014Proceedings of COMMA 2012, Vienna, Austria, September 10\u201312, 2012","author":"Hunter"},{"key":"2023030410205131400_","first-page":"428","article-title":"PySAT: a Python toolkit for prototyping with SAT oracles","author":"Ignatiev","year":"2018","journal-title":"In SAT"},{"key":"2023030410205131400_","first-page":"928","article-title":"CoQuiAAS: a constraint-based quick abstract argumentation solver","volume-title":"27th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2015, Vietri sul Mare, Italy, November 9\u201311, 2015","author":"Lagniez","year":"2015"},{"key":"2023030410205131400_","first-page":"80","article-title":"Introducing the fourth international competition on computational models of argumentation","volume-title":"Proceedings of the Third International Workshop on Systems and Algorithms for Formal Argumentation co-located with the 8th International Conference on Computational Models of Argument (COMMA 2020), September 8, 2020","author":"Lagniez","year":"2020"},{"key":"2023030410205131400_","article-title":"Design and results of ICCMA 2021","author":"Lagniez","year":"2021"},{"key":"2023030410205131400_","doi-asserted-by":"crossref","first-page":"765","DOI":"10.1162\/coli_a_00364","article-title":"Argument mining: a survey","volume":"45","author":"Lawrence","year":"2019","journal-title":"Computational Linguistics"},{"key":"2023030410205131400_","first-page":"1","article-title":"Probabilistic argumentation frameworks","volume-title":"Proceedings of the First International Workshop on Theory and Applications of Formal Argumentation (TAFA\u201911)","author":"Li","year":"2011"},{"key":"2023030410205131400_","first-page":"283","article-title":"Possible controllability of control argumentation frameworks","volume-title":"8th International Conference on Computational Models of Argument (COMMA 2020)","author":"Mailly","year":"2020"},{"key":"2023030410205131400_","first-page":"103","article-title":"Constrained incomplete argumentation frameworks","volume-title":"Symbolic and Quantitative Approaches to Reasoning with Uncertainty\u201416th European Conference, ECSQARU 2021, Prague, Czech Republic, September 21\u201324, 2021, Proceedings","author":"Mailly","year":"2021"},{"key":"2023030410205131400_","first-page":"322","article-title":"Extension-based semantics for incomplete argumentation frameworks","volume-title":"Logic and Argumentation\u20144th International Conference, CLAR 2021, Hangzhou, China, October 20\u201322, 2021, Proceedings","author":"Mailly","year":"2021"},{"key":"2023030410205131400_","doi-asserted-by":"crossref","first-page":"291","DOI":"10.3233\/AAC-210010","article-title":"Yes, no, maybe, I don\u2019t know: complexity and application of abstract argumentation with incomplete knowledge","volume":"13","author":"Mailly","year":"2022","journal-title":"Argument & Computation"},{"key":"2023030410205131400_","first-page":"800","article-title":"toksia: an efficient abstract argumentation reasoner","volume-title":"Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020, Rhodes, Greece, September 12\u201318, 2020","author":"Niskanen","year":"2020"},{"key":"2023030410205131400_","first-page":"1855","article-title":"Controllability of control argumentation frameworks","volume-title":"Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020","author":"Niskanen","year":"2020"},{"key":"2023030410205131400_","first-page":"2942","article-title":"Deciding acceptance in incomplete argumentation frameworks","volume-title":"34th AAAI Conference on Artificial Intelligence (AAAI 2020)","author":"Niskanen","year":"2020"},{"key":"2023030410205131400_","doi-asserted-by":"crossref","first-page":"87","DOI":"10.3233\/AAC-200904","article-title":"United we stand: accruals in strength-based argumentation","volume":"12","author":"Rossit","year":"2021","journal-title":"Argument & Computation"},{"key":"2023030410205131400_","first-page":"115","article-title":"On the complexity of derivation in propositional calculus","volume-title":"Studies in Constructive Mathematics and Mathematical Logic, Part II, Seminars in Mathematics","author":"Tseytin","year":"1970"},{"key":"2023030410205131400_","first-page":"797","article-title":"The principle-based approach to abstract argumentation semantics","volume-title":"Handbook of Formal Argumentation","author":"van der Torre","year":"2018"},{"key":"2023030410205131400_","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","article-title":"Collective dynamics of \u201csmall-world\u201d networks","volume":"393","author":"Watts","year":"1998","journal-title":"Nature"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/33\/2\/406\/49408964\/exac099.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/33\/2\/406\/49408964\/exac099.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,18]],"date-time":"2023-03-18T08:06:06Z","timestamp":1679126766000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/33\/2\/406\/7000822"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,25]]},"references-count":47,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2023,1,25]]},"published-print":{"date-parts":[[2023,3,2]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exac099","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,3]]},"published":{"date-parts":[[2023,1,25]]}}}