Research map / Learning theory and algorithms / Combinatorial and search optimization
Complexity of Credulous and Skeptical Acceptance in Epistemic Argumentation Framework
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.
Studies the complexity of credulous and skeptical acceptance in epistemic argumentation frameworks (EAF), introduces Labelled CAF (LCAF), and shows EAF matches LCAF complexity and is more expressive than iAF under preferred semantics.
Problem
Complexity of credulous and skeptical acceptance in epistemic argumentation frameworks was unexplored, and the relationships among EAF, constrained AF, and incomplete AF were unclear.
Approach
Introduces LCAF, a constrained AF whose constraints are propositional formulas over labelled arguments (in/out/und), show LCAF is an EAF without modal operators, and reduce iAF acceptance to LCAF/EAF; then proves EAF has the same complexity as LCAF, with complexity results completed for each semantics.
Key results
- Credulous acceptance under preferred and semi-stable semantics is Σp2-complete for both LCAF and EAF, while under co and st it is NP-complete.
- Skeptical acceptance under preferred and semi-stable semantics is Πp2-complete for both LCAF and EAF; under co and st it is coNP-complete.
- EAF is shown to be more expressive than iAF under preferred semantics, since iAF credulous acceptance under preferred is NP-complete while EAF's is Σp2-complete.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add constraints over labeled arguments (LCAF) | AF · Preferred semantics | Credulous acceptance complexity: NP-c -> Σp₂-c | Mixed |
| Add epistemic constraints, including modal operators (EAF) | LCAF · Credulous and skeptical acceptance | Acceptance complexity | No clear effect |
| Encode iAF acceptance as LCAF acceptance | iAF · Preferred semantics | Credulous acceptance complexity: NP-c -> Σp₂-c | Helped |
Surprising findings
- Although LCAF is a restriction of EAF without modal operators, both have identical complexity for all considered problems.
Limitations
- Open problem: translating an EAF into an equivalent LCAF is not established.
- Only epistemic constraints of a restricted normal form are considered; aggregate constraints are left to future work.
Experimental setup
Metrics: complexity class completeness
Baselines: constrained AF (Alfano et al. 2021b) incomplete AF (Baumeister et al. 2021)
Builds on: Dung's argumentation framework epistemic argumentation framework (Sakama and Son 2020) constrained argumentation frameworks incomplete argumentation frameworks
Closest papers by meaning
- Incomplete Argumentation Frameworks: Properties and Complexity (AAAI 2022 · similarity 0.92)
- Argumentative Large Language Models for Explainable and Contestable Claim Verification (AAAI 2025 · similarity 0.87)
- Defeasible Normative Reasoning: A Proof-Theoretic Integration of Logical Argumentation (AAAI 2024 · similarity 0.87)
- Non-flat ABA Is an Instance of Bipolar Argumentation (AAAI 2024 · similarity 0.86)
- Dung’s Argumentation Framework: Unveiling the Expressive Power with Inconsistent Databases (AAAI 2025 · similarity 0.86)
- Redefining ABA+ Semantics via Abstract Set-to-Set Attacks (AAAI 2024 · 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.