Research map / Learning theory and algorithms / Combinatorial and search optimization
Dung’s Argumentation Framework: Unveiling the Expressive Power with Inconsistent Databases
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that Dung abstract argumentation frameworks can be translated in polynomial time into inconsistent databases with functional and inclusion dependencies, relating AF semantics to subset and attribute-based (covering) repairs.
Problem
The exact expressive power of Dung's abstract argumentation frameworks relative to inconsistent databases and integrity constraints was unexplored; prior work only translated databases into AFs.
Approach
Encode each argument as a tuple, attacks as FDs (conflict database via edge-coloring with at most degree+1 FDs) and defense as IDs (defense database), so that conflict-free, naive, admissible and preferred extensions correspond to subset repairs; additionally define maximal content-preserving (covering) attribute-based repairs that match stable, semi-stable and stage semantics.
Key results
- AF-database table size is |A| x 3(|A|+1) with at most |A| FDs and |A|+1 IDs, constructible in polynomial time, so each AF is simulated by an inconsistent database.
- Conflict-free and naive extensions correspond to repairs and maximal repairs of the conflict database, and admissible and preferred extensions to repairs and maximal repairs of the full AF-database.
- Stable, stage and semi-stable extensions correspond to fully covering or maximally covering repairs with respect to range attributes.
Surprising findings
- FDs alone cannot simulate AFs with directed attacks; the translation treats attacks as symmetric and an AF cannot be simulated by only FDs or only IDs unless P = NP.
Limitations
- Complete and grounded semantics have no natural counterpart in the subset-repair setting with FDs and IDs.
- Complexity analysis of maximally and fully covering repairs is left for future work.
- Self-attacking arguments require an extra ID; symmetric treatment of attacks in the conflict database.
Experimental setup
Builds on: Dung's abstract argumentation framework subset repairs for inconsistent databases Vizing's theorem
Closest papers by meaning
- Argumentation Frameworks with Strong and Weak Constraints: Semantics and Complexity (AAAI 2021 · similarity 0.91)
- Redefining ABA+ Semantics via Abstract Set-to-Set Attacks (AAAI 2024 · similarity 0.88)
- Non-flat ABA Is an Instance of Bipolar Argumentation (AAAI 2024 · similarity 0.86)
- Defeasible Normative Reasoning: A Proof-Theoretic Integration of Logical Argumentation (AAAI 2024 · similarity 0.86)
- Complexity of Credulous and Skeptical Acceptance in Epistemic Argumentation Framework (AAAI 2024 · similarity 0.86)
- Argumentative Large Language Models for Explainable and Contestable Claim Verification (AAAI 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.