{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:44:52Z","timestamp":1740123892193,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"11-12","license":[{"start":{"date-parts":[[2022,3,26]],"date-time":"2022-03-26T00:00:00Z","timestamp":1648252800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,26]],"date-time":"2022-03-26T00:00:00Z","timestamp":1648252800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Max Planck Institute for Informatics"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper we investigate, from a graph theoretical point of view, the notion of acceptability in Dung semantics for abstract argumentation frameworks. We advance the state of the art by introducing and analyzing combinatorial structures exploited for taming, in particular cases, the exponential blowout of acceptance algorithms. We conclude the paper by a series of observations allowing to deepen the intuition with respect to the practical use of Dung acceptance based semantics.<\/jats:p>","DOI":"10.1007\/s10472-022-09785-3","type":"journal-article","created":{"date-parts":[[2022,3,26]],"date-time":"2022-03-26T04:32:49Z","timestamp":1648269169000},"page":"1139-1158","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Indepth combinatorial analysis of admissible sets for abstract argumentation"],"prefix":"10.1007","volume":"90","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1731-4386","authenticated-orcid":false,"given":"Cosmina","family":"Croitoru","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Madalina","family":"Croitoru","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,3,26]]},"reference":[{"key":"9785_CR1","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1016\/j.artint.2007.04.004","volume":"171","author":"P Baroni","year":"2007","unstructured":"Baroni, P., Giacomin, M.: On principle-based evaluation of extension-based argumentation semantics. Artif. Intell. 171, 675\u2013700 (2007)","journal-title":"Artif. Intell."},{"key":"9785_CR2","doi-asserted-by":"crossref","unstructured":"Baumann, R., Brewka, G., Ulbricht, M.: Comparing weak admissibility semantics to their dung-style counterparts - reduct, modularization, and strong equivalence in abstract argumentation. In: KR, pp. 79\u201388 (2020)","DOI":"10.24963\/kr.2020\/9"},{"key":"9785_CR3","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/j.jet.2011.03.006","volume":"146","author":"F Brandt","year":"2011","unstructured":"Brandt, F., Harrenstein, P.: Set-Rationalizable Choice functions and self- stability. J. Econ. Theory 146, 233\u2013273 (2011)","journal-title":"J. Econ. Theory"},{"key":"9785_CR4","doi-asserted-by":"crossref","unstructured":"Caminada, M.: On the issue of reinstatement in argumentation. In: Proc. of Logics in Artificial Intelligence, 10Th European Conference, JELIA, LNCS 4160, vol. 4160, pp 112\u2013123. Springer, Berlin (2006)","DOI":"10.1007\/11853886_11"},{"key":"9785_CR5","first-page":"121","volume":"144","author":"M Caminada","year":"2006","unstructured":"Caminada, M.: Semi-Stable Semantics. Proc. of COMMA 2006, IOS Press 144, 121\u2013130 (2006)","journal-title":"Proc. of COMMA 2006, IOS Press"},{"key":"9785_CR6","unstructured":"Caminada, M.: Comparing two unique extension semantics for formal argumentation: ideal and eager. In: Proc. of the 19th Belgian-Dutch Conference on Artificial Intelligence (BNAIC 2007), pp 81\u201387, Utrecht University Press (2007)"},{"issue":"3","key":"9785_CR7","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1093\/logcom\/13.3.377","volume":"13","author":"C Cayrol","year":"2003","unstructured":"Cayrol, C., Doutre, S., Mengin, J.: On decision problems related to the preferred semantics for argumentation frameworks. Journal of Logic and Computation 13(3), 377\u2013403 (2003)","journal-title":"Journal of Logic and Computation"},{"key":"9785_CR8","doi-asserted-by":"crossref","unstructured":"Charwat, G., Dvor\u00e1k, W., Gaggle, S.A., Wallner, J.P., Woltran, S.: Methods for solving reasoning problems in abstract argumentation - a survey. Artif. Intell., pp. 28\u201363 (2015)","DOI":"10.1016\/j.artint.2014.11.008"},{"key":"9785_CR9","unstructured":"Chv\u00e1tal, V: On the Computational Complexity of Finding a Kernel. Tech Rep. Centre de Recherches Math\u00e9matiques, Universit\u00e9 de Montr\u00e9al (1973)"},{"key":"9785_CR10","doi-asserted-by":"crossref","unstructured":"Chv\u00e1tal, V., Lov\u00e1sz, L.: Every directed graph has a semi-kernel, vol. 411, p 175 (1974)","DOI":"10.1007\/BFb0066192"},{"issue":"11","key":"9785_CR11","doi-asserted-by":"publisher","first-page":"863","DOI":"10.1016\/j.ipl.2015.06.017","volume":"115","author":"C Croitoru","year":"2015","unstructured":"Croitoru, C.: A note on quasi-kernels in digraphs. Inf. Process. Lett. 115(11), 863\u2013865 (2015)","journal-title":"Inf. Process. Lett."},{"key":"9785_CR12","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/S0304-3975(96)80707-9","volume":"170","author":"Y Dimopoulos","year":"1996","unstructured":"Dimopoulos, Y., Torres, A.: Graph theoretical structures in logic programs and default theories. Theoret Comput Sci 170, 209\u2013244 (1996)","journal-title":"Theoret Comput Sci"},{"key":"9785_CR13","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/0004-3702(94)00041-X","volume":"77","author":"PM Dung","year":"1995","unstructured":"Dung, P.M.: On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artif. Intell. 77, 321\u2013357 (1995)","journal-title":"Artif. Intell."},{"key":"9785_CR14","unstructured":"Dung, P.M., Mancarella, P., Toni, F.: A Dialectic Procedure for Sceptical Assumption-Based Argumentation Proc. of COMMA 2006, IOS Press, vol. 144, pp 145\u2013146 (2006)"},{"key":"9785_CR15","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1016\/j.artint.2007.03.006","volume":"171","author":"PE Dunne","year":"2007","unstructured":"Dunne, P.E.: Computational properties of argument systems satisfying graph-theoretic constraints. Artif. Intell. 171, 701\u2013729 (2007)","journal-title":"Artif. Intell."},{"key":"9785_CR16","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/S0004-3702(02)00261-8","volume":"141","author":"PE Dunne","year":"2002","unstructured":"Dunne, P.E., Bench-Capon, T.: Coherence in finite argument systems. Artif. Intell. 141, 187\u2013203 (2002)","journal-title":"Artif. Intell."},{"key":"9785_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2013.06.004","volume":"202","author":"PE Dunne","year":"2013","unstructured":"Dunne, P.E., Dvor\u00e1k, W., Woltran, S.: Parametric properties of ideal semantics. Artif. Intell. 202, 1\u201328 (2013)","journal-title":"Artif. Intell."},{"key":"9785_CR18","first-page":"631","volume":"14","author":"W Dvor\u00e1k","year":"2018","unstructured":"Dvor\u00e1k, W., Dunne, P.E.: Computational Problems in Formal Argumentation and their Complexity. Handbook of Formal Argumentation, Chap 14, 631\u2013687 (2018)","journal-title":"Handbook of Formal Argumentation, Chap"},{"key":"9785_CR19","first-page":"100","volume":"4","author":"A Fraenkel","year":"1997","unstructured":"Fraenkel, A.: Combinatorial game theory foundations applied to digraph kernels. Electron. J. Comb. 4, 100\u2013117 (1997)","journal-title":"Electron. J. Comb."},{"key":"9785_CR20","doi-asserted-by":"crossref","unstructured":"Grossi, D., Modgil, S.: On the graded acceptability of arguments in abstract and instantiated argumentation. Artif Intell, pp. 138\u2013173 (2019)","DOI":"10.1016\/j.artint.2019.05.001"},{"key":"9785_CR21","doi-asserted-by":"crossref","unstructured":"Heusner, M., Keller, T., Helmert, M.: Understanding the search behavior of gbfs. In: Proceedings of SOCS, vol. 2017, pp 47\u201355 (2017)","DOI":"10.1609\/socs.v8i1.18425"},{"key":"9785_CR22","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.artint.2013.11.001","volume":"207","author":"S Nofal","year":"2014","unstructured":"Nofal, S., Atkinson, K., Dunne, P.E.: Algorithms for decision problems in argument systems under preferred semantics. Artif. Intell. 207, 23\u201351 (2014)","journal-title":"Artif. Intell."},{"key":"9785_CR23","doi-asserted-by":"crossref","unstructured":"Nofal, S., Atkinson, K., Dunne, E.P.: On checking skeptical and ideal admissibility in abstract argumentation frameworks. Inf Process Lett, pp. 7\u201312 (2019)","DOI":"10.1016\/j.ipl.2019.03.013"},{"key":"9785_CR24","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/1887.001.0001","volume-title":"Cognitive Carpentry a Blueprint for How to Build a Person","author":"JL Pollock","year":"1995","unstructured":"Pollock, J.L.: Cognitive Carpentry a Blueprint for How to Build a Person. MIT Press, Cambridge (1995)"},{"key":"9785_CR25","unstructured":"Thimm, M.: Dredd - A heuristics-guided backtracking solver with information propagation for abstract argumentation. In: The Third International Competition on Computational Models of Argumentation (2019)"}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-022-09785-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10472-022-09785-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-022-09785-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,28]],"date-time":"2022-11-28T08:17:41Z","timestamp":1669623461000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10472-022-09785-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,26]]},"references-count":25,"journal-issue":{"issue":"11-12","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["9785"],"URL":"https:\/\/doi.org\/10.1007\/s10472-022-09785-3","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"type":"print","value":"1012-2443"},{"type":"electronic","value":"1573-7470"}],"subject":[],"published":{"date-parts":[[2022,3,26]]},"assertion":[{"value":"10 January 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 March 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflicts of interest to declare. All co-authors have seen and agree with the contents of the manuscript and there is no financial interest to report.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"<!--Emphasis Type='Bold' removed-->Conflict of Interests"}}]}}