Research map / Learning theory and algorithms / Combinatorial and search optimization
Redefining ABA+ Semantics via Abstract Set-to-Set Attacks
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.
Introduces Hyper Argumentation Frameworks (set-to-set attacks) to give an abstract instantiation of ABA+ and proposes Θ-complete and Θ-grounded semantics that always yield extensions.
Problem
ABA+ lacks an abstract graph-based instantiation, and its complete and grounded semantics may have no extension, since preference-reversed attacks have multi-element heads.
Approach
Generalize Dung AFs to hyperframeworks with set-to-set attacks, show ABA+ maps semantics-preservingly onto them, and refine the characteristic function into a closure operator ΘF so that Θ-complete and Θ-grounded extensions always exist while generalizing the AF semantics.
Key results
- Shows HYPAFs capture ABA+ semantics (adm, com, grd, pref, stb) via a semantics-preserving translation (Theorem 17).
- Θ-complete and Θ-grounded semantics always exist; Θ-grounded extension is unique (Proposition 42).
- Settles complexity of several ABA+ semantics; Θ-grd and skeptical Θ-com are less demanding than traditional variants (Table 1).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the characteristic-function completeness test Γ with the closure function Θ | HYPAFs · HYPAFs generally | existence of complete and grounded extensions | Helped |
| Use Θ-grounded semantics instead of traditional grounded semantics | ABA+ · Skeptical acceptance | computational complexity | Helped |
| Translate ABA+ frameworks into Hyper Argumentation Frameworks | ABA+ · ABA+ semantics | semantics correspondence | Helped |
Surprising findings
- ABA+ frameworks, and the induced HYPAFs, can have no complete or grounded extension, even for a simple three-assumption example.
Limitations
- Translation covers only HYPAFs where either head or tail of each attack has size one, so not arbitrary HYPAFs.
- Generalized Θ-grounded semantics for HYPAFs is not necessarily the least fixed point of the characteristic function in all cases; standard grounded fixed-point computation only guaranteed when admissible.
- Some tight complexity bounds remain open.
Experimental setup
Metrics: complexity class of verification, credulous and skeptical ac
Baselines: SETAF semantics (Nielsen and Parsons 2006) ABA+ complete semantics ABA+ grounded semantics
Builds on: Dung abstract argumentation frameworks ABA+ (Cyras and Toni 2016) SETAFs (Nielsen and Parsons 2006) Lehtonen et al. 2021 ABA+ complexity
Closest papers by meaning
- Non-flat ABA Is an Instance of Bipolar Argumentation (AAAI 2024 · similarity 0.93)
- Reasoning over Assumption-Based Argumentation Frameworks via Direct Answer Set Programming Encodings (AAAI 2019 · similarity 0.92)
- On Undisputed Sets in Abstract Argumentation (AAAI 2023 · similarity 0.90)
- Tractable Abstract Argumentation via Backdoor-Treewidth (AAAI 2022 · similarity 0.90)
- Under-Approximating Semantics in Clustered Assumption-Based Argumentation (AAAI 2026 · similarity 0.89)
- Dung’s Argumentation Framework: Unveiling the Expressive Power with Inconsistent Databases (AAAI 2025 · similarity 0.88)
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.