Computer Science Institute, Leipzig Universityhttps://ror.org/03s7gtk40, Leipzig, Germany"/> Center for Scalable Data Analytics and Artificial Intelligence (ScaDS.AI) Dresden/Leipzig, Leipzig University, Leipzig, Germany"/>
Search
  • All Journals
Advanced Search
Search articles by Title, Author, Keywords, DOI
Submit Manuscript
7.7CiteScore
2.0Impact Factor
Advanced Search
MAP  >  The Knowledge Engineering Review
2025 Volume 40
Article Contents
Next Previous
RESEARCH ARTICLE   Open Access    

Characterizing conflict-free and naive labellings—realizabiliy, uniqueness and patterns of redundancy

  • Computer Science Institute, Leipzig Universityhttps://ror.org/03s7gtk40, Leipzig, Germany

  • Center for Scalable Data Analytics and Artificial Intelligence (ScaDS.AI) Dresden/Leipzig, Leipzig University, Leipzig, Germany

More Information
  • Abstract: The article is concerned with realizability in abstract argumentation. It provides characterization theorems for the most basic types of labelling-based semantics, namely conflict-free and naive labellings. It turns out that existing characterizations for extension-based semantics are of little help in characterizing labelling-based semantics. To this end, we introduce several new criteria like L-tightness, reject-witnessing, reject-compositionality as well as the new construct of a labelling-downward-closure, which help determine whether a given set of labellings is realizable regarding conflict-free or naive semantics. Moreover, we present standard constructions and analyse their uniqueness status. Further classical concepts like ordinary and strong equivalence are studied too. Last but not least, we delve into the characterization of stable labellings. It turns out that this endeavour is a highly non-trivial task with many parallels to so-called compact realizability, an open problem for stable semantics in abstract argumentation.
  • 加载中
  • Alchourrón , C. E., Gärdenfors , P. & Makinson , D. 1985. On the logic of theory change: Partial meet contraction and revision functions. Journal of Symbolic Logic 50(2), 510–530.10.2307/2274239

    Google Scholar

    Arieli , O. 2012. Conflict-tolerant semantics for argumentation frameworks. In Logics in Artificial Intelligence - 13th European Conference, JELIA 2012, Toulouse, France, September 26–28, 2012. Proceedings, Lecture Notes in Computer Science 7519, 28–40. Springer.10.1007/978-3-642-33353-8_3

    Google Scholar

    Atkinson , K., Baroni , P., Giacomin , M., Hunter , A., Prakken , H., Reed , C., Simari , G. R., Thimm , M. & Villata , S. 2017. Towards artificial argumentation. AI Magazine 38(3), 25–36.10.1609/aimag.v38i3.2704

    Google Scholar

    Baroni , P., Caminada , M. & Giacomin , M. 2018a. Abstract argumentation frameworks and their semantics. In Handbook of Formal Argumentation, Baroni , P., Gabbay , D., Giacomin , M. & van der Torre , L. (eds), chapter 4. College Publications.

    Google Scholar

    Baroni , P., Gabbay , D., Giacomin , M. & van der Torre , L. 2018b. Handbook of Formal Argumentation. College Publications.

    Google Scholar

    Baumann , R. 2012. What does it take to enforce an argument? minimal change in abstract argumentation. In 20th European Conference on Artificial Intelligence, 127–132.

    Google Scholar

    Baumann , R. 2016. Characterizing equivalence notions for labelling-based semantics. In Principles of Knowledge Representation and Reasoning: Proceedings of the Fifteenth International Conference, KR 2016, Cape Town, South Africa, April 25–29, 2016, 22–32. AAAI Press.

    Google Scholar

    Baumann , R. 2018. On the nature of argumentation semantics: Existence and uniqueness, expressibility, and replaceability. In Handbook of Formal Argumentation, chapter 14. College Publications.

    Google Scholar

    Baumann , R., Berthold , M., Gabbay , D. M. & Rodrigues , O. 2025. Forgetting in abstract argumentation: Limits and possibilities. Journal of Artificial Intelligence Research 82.

    Google Scholar

    Baumann , R. & Brewka , G. 2010. Expanding argumentation frameworks: Enforcing and monotonicity results. In Computational Models of Argument: Proceedings of COMMA 2010, Desenzano del Garda, Italy, September 8–10, 2010, 75–86.

    Google Scholar

    Baumann , R., Brewka , G. & Ulbricht , M. 2022. Shedding new light on the foundations of abstract argumentation: Modularization and weak admissibility. Artificial Intelligence 310, 103742.10.1016/j.artint.2022.103742

    Google Scholar

    Baumann , R., Doutre , S., Mailly , J. & Wallner , J. P. 2021. Enforcement in formal argumentation. FLAP 8(6), 1623–1678.

    Google Scholar

    Baumann , R., Dvorák , W., Linsbichler , T., Strass , H. & Woltran , S. 2014. Compact argumentation frameworks. In 21st European Conference on Artificial Intelligence, 69–74. IOS Press.

    Google Scholar

    Baumann , R., Gabbay , D. M. & Rodrigues , O. 2020. Forgetting an argument. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7–12, 2020, 2750–2757.

    Google Scholar

    Baumann , R. & Heine , A. 2023. On conflict-free labellings - realizability, construction and patterns of redundancy. In Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning, KR 2023, Rhodes, Greece, September 2–8, 2023, 720–725. AAAI Press.10.24963/kr.2023/70

    Google Scholar

    Baumann , R. & Heine , A. 2024. On naive labellings - realizability, construction and patterns of redundancy. In Foundations of Information and Knowledge Systems 13th International Symposium, 125–143. Springer.10.1007/978-3-031-56940-1_7

    Google Scholar

    Baumann , R., Linsbichler , T. & Woltran , S. 2016. Verifiability of argumentation semantics. In Computational Models of Argument - Proceedings of COMMA 2016, Potsdam, Germany, 12–16 September, 2016, Baroni , P., Gordon , T. F., Scheffler , T. & Stede , M. (eds). Frontiers in Artificial Intelligence and Applications 287, 83–94. IOS Press.

    Google Scholar

    Baumann , R. & Spanring , C. 2015. Infinite argumentation frameworks - On the existence and uniqueness of extensions. In Essays Dedicated to Gerhard Brewka on the Occasion of His 60th Birthday, 9060, 281–295. Springer.10.1007/978-3-319-14726-0_19

    Google Scholar

    Baumann , R. & Spanring , C. 2017. A study of unrestricted abstract argumentation frameworks. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19–25, 2017, 807–813.

    Google Scholar

    Bench-Capon , T. J. M. & Dunne , P. E. 2007. Argumentation in artificial intelligence. Artificial Intelligence 171(10-15), 619–641.10.1016/j.artint.2007.05.001

    Google Scholar

    Besnard , P., Garcia , A., Hunter , A., Modgil , S., Prakken , H., Simari , G. & Toni , F. 2014. Introduction to structured argumentation. Argument & Computation 5(1), 1–4.10.1080/19462166.2013.869764

    Google Scholar

    Bisquert , P., Cayrol , C., de Saint-Cyr , F. D. & Lagasquie-Schiex , M. 2011. Change in argumentation systems: Exploring the interest of removing an argument. In Scalable Uncertainty Management - 5th International Conference, SUM 2011, 275–288.

    Google Scholar

    Caminada , M. 2011. A labelling approach for ideal and stage semantics. Argument & Computation 2(1), 1–21.10.1080/19462166.2010.515036

    Google Scholar

    Dung , P. M. 1995. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artificial Intelligence 77(2), 321–358.10.1016/0004-3702(94)00041-X

    Google Scholar

    Dunne , P. E., Dvorák , W., Linsbichler , T. & Woltran , S. 2014. Characteristics of multiple viewpoints in abstract argumentation. In Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, KR 2014, Vienna, Austria, July 20–24, 2014, Baral , C., Giacomo , G. D. & Eiter , T. (eds). AAAI Press.

    Google Scholar

    Dunne , P. E., Dvorák , W., Linsbichler , T. & Woltran , S. 2015. Characteristics of multiple viewpoints in abstract argumentation. Artificial Intelligence 228, 153–178.10.1016/j.artint.2015.07.006

    Google Scholar

    Dvorák , W., Järvisalo , M., Linsbichler , T., Niskanen , A. & Woltran , S. 2019. Preprocessing argumentation frameworks via replacement patterns. In Logics in Artificial Intelligence - 16th European Conference, JELIA 2019, Rende, Italy, May 7–11, 2019, Proceedings, 116–132. Springer.10.1007/978-3-030-19570-0_8

    Google Scholar

    Dyrkolbotn , S. K. 2014. How to argue for anything: Enforcing arbitrary sets of labellings using afs. In Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, KR 2014, Vienna, Austria, July 20–24, 2014, Baral , C., Giacomo , G. D. & Eiter , T. (eds). AAAI Press.

    Google Scholar

    Eiter , T., Fink , M., Pührer , J., Tompits , H. & Woltran , S. 2013. Model-based recasting in answer-set programming. Journal of Applied Non-Classical Logics 23(1-2), 75–104.10.1080/11663081.2013.799318

    Google Scholar

    Eiter , T. & Kern-Isberner , G. 2019. A brief survey on forgetting from a knowledge representation and reasoning perspective. Künstliche Intelligenz 33(1), 9–33.10.1007/s13218-018-0564-6

    Google Scholar

    Gelfond , M. & Lifschitz , V. 1988. The stable model semantics for logic programming. In Logic Programming, Proceedings of the Fifth International Conference and Symposium, Seattle, Washington, USA, August 15–19, 1988 (2 Volumes), 1070–1080.

    Google Scholar

    Linsbichler , T., Pührer , J. & Strass , H. 2016. A uniform account of realizability in abstract argumentation. In 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), Kaminka , G. A., Fox , M., Bouquet , P., Hüllermeier , E., Dignum , V., Dignum , F. & van Harmelen , F. (eds), Frontiers in Artificial Intelligence and Applications 285, 252–260. IOS Press.

    Google Scholar

    Niskanen , A., Wallner , J. & Järvisalo , M. 2019. Synthesizing argumentation frameworks from examples. Journal of Artificial Intelligence Research 66, 503–554.10.1613/jair.1.11758

    Google Scholar

    Oikarinen , E. & Woltran , S. 2011. Characterizing strong equivalence for argumentation frameworks. Artificial Intelligence 175(14-15), 1985–2009.10.1016/j.artint.2011.06.003

    Google Scholar

    Strass , H. 2015. The relative expressiveness of abstract argumentation and logic programming. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25–30, 2015, Austin, Texas, USA, 1625–1631. AAAI Press.

    Google Scholar

    van der Torre , L. & Vesic , S. 2017. The principle-based approach to abstract argumentation semantics. FLAP 4(8).

    Google Scholar

    Wallner , J. P., Niskanen , A. & Järvisalo , M. 2017. Complexity results and algorithms for extension enforcement in abstract argumentation. Journal of Artificial Intelligence Research 60, 1–40.10.1613/jair.5415

    Google Scholar

  • Cite this article

    Ringo Baumann, Anne-Marie Heine. 2025. Characterizing conflict-free and naive labellings—realizabiliy, uniqueness and patterns of redundancy. The Knowledge Engineering Review 40(1), doi: 10.1017/S0269888925100064
    Ringo Baumann, Anne-Marie Heine. 2025. Characterizing conflict-free and naive labellings—realizabiliy, uniqueness and patterns of redundancy. The Knowledge Engineering Review 40(1), doi: 10.1017/S0269888925100064
    shu
Download PDF

Article Metrics

Article views(87) PDF downloads(90)

Other Articles By Authors

RESEARCH ARTICLE   Open Access    

Characterizing conflict-free and naive labellings—realizabiliy, uniqueness and patterns of redundancy

  • Computer Science Institute, Leipzig Universityhttps://ror.org/03s7gtk40, Leipzig, Germany

  • Center for Scalable Data Analytics and Artificial Intelligence (ScaDS.AI) Dresden/Leipzig, Leipzig University, Leipzig, Germany

  • Received: 13 December 2024
  • Revised: 02 September 2025
  • Accepted: 04 September 2025
  • Published online: 05 December 2025
The Knowledge Engineering Review  40,  2025, 40(1)  |  Cite this article

Abstract: Abstract: The article is concerned with realizability in abstract argumentation. It provides characterization theorems for the most basic types of labelling-based semantics, namely conflict-free and naive labellings. It turns out that existing characterizations for extension-based semantics are of little help in characterizing labelling-based semantics. To this end, we introduce several new criteria like L-tightness, reject-witnessing, reject-compositionality as well as the new construct of a labelling-downward-closure, which help determine whether a given set of labellings is realizable regarding conflict-free or naive semantics. Moreover, we present standard constructions and analyse their uniqueness status. Further classical concepts like ordinary and strong equivalence are studied too. Last but not least, we delve into the characterization of stable labellings. It turns out that this endeavour is a highly non-trivial task with many parallels to so-called compact realizability, an open problem for stable semantics in abstract argumentation.

    HTML

    Acknowledgments

    • This work was supported by the German Research Foundation (DFG, BA 6170/3-1) and by the German Federal Ministry of Education and Research (BMBF, 01/S18026A-F) by funding the competence center for Big Data and AI ‘ScaDS.AI’ Dresden/Leipzig.

    • This relation is a general interaction between both kinds of semantics. Confer Baumann (2018), Theorem 7 for more information.

    Rights and permissions
    • This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.
References (37)
  • About this article
    Cite this article
    Ringo Baumann, Anne-Marie Heine. 2025. Characterizing conflict-free and naive labellings—realizabiliy, uniqueness and patterns of redundancy. The Knowledge Engineering Review 40(1), doi: 10.1017/S0269888925100064
    Ringo Baumann, Anne-Marie Heine. 2025. Characterizing conflict-free and naive labellings—realizabiliy, uniqueness and patterns of redundancy. The Knowledge Engineering Review 40(1), doi: 10.1017/S0269888925100064
    shu

    • Catalog

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return