Research map / Learning theory and algorithms / Combinatorial and search optimization
Recursion in Abstract Argumentation is Hard — On the Complexity of Semantics Based on Weak Admissibility
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use weak admissibility instead of classical admissibility | Argumentation semantics on general AFs · General AF | Credulous acceptance complexity: NP-c -> PSPACE-c | Mixed |
| Use weak admissibility instead of classical admissibility | Argumentation semantics on general AFs · General AF | Extension verification complexity: in P -> PSPACE-c | Mixed |
| Use weak complete semantics instead of classical complete semantics | Argumentation semantics on general AFs · General AF | Skeptical acceptance complexity: P-c -> PSPACE-c | Mixed |
| Use weak preferred semantics instead of classical preferred semantics | Argumentation semantics on general AFs · General AF | Skeptical acceptance complexity: ΠP2-c -> PSPACE-c | Mixed |
| Restrict frameworks to symmetric AFs | Weak admissibility-based semantics · Symmetric AFs | Credulous and skeptical acceptance complexity: PSPACE-complete -> P | Helped |
| Restrict frameworks to acyclic AFs | Weak admissibility-based semantics · Acyclic AFs | Credulous and skeptical acceptance complexity: PSPACE-complete -> in P | Helped |
| Restrict frameworks to odd-cycle free AFs | Weak admissible, weak complete, and weak preferred semantics · Odd-cycle free AFs | Credulous acceptance complexity: PSPACE-complete -> NP-complete | Helped |
| Restrict frameworks to odd-cycle free AFs | Weak complete and weak grounded semantics · Odd-cycle free AFs | Skeptical acceptance complexity: PSPACE-complete -> coNP-complete | Helped |
| Restrict frameworks to bipartite AFs | Weak admissibility-based semantics · Bipartite AFs | Credulous and skeptical acceptance complexity: PSPACE-complete -> in P | Helped |
| Use weak preferred rather than classical preferred semantics | Argumentation frameworks with no even cycles · No-even AFs | Number of preferred extensions | Mixed |
Closest papers by meaning
- On Undisputed Sets in Abstract Argumentation (AAAI 2023 · similarity 0.92)
- Bilateral Gradual Semantics for Weighted Argumentation (AAAI 2024 · similarity 0.88)
- Dung’s Argumentation Framework: Unveiling the Expressive Power with Inconsistent Databases (AAAI 2025 · similarity 0.88)
- Non-flat ABA Is an Instance of Bipolar Argumentation (AAAI 2024 · similarity 0.87)
- Redefining ABA+ Semantics via Abstract Set-to-Set Attacks (AAAI 2024 · similarity 0.87)
- Complexity of Credulous and Skeptical Acceptance in Epistemic Argumentation Framework (AAAI 2024 · similarity 0.87)
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.