TL;DR
This paper introduces "initial models" for Abstract Dialectical Frameworks (ADFs), a generalization of initial sets in abstract argumentation. They then extend the concept of "serialisability" to ADFs, providing a procedural, step-by-step way to understand how acceptable models are constructed, which brings dialectical reasoning closer to the semantics of ADFs.
What Problem Does This Paper Address?
Abstract Dialectical Frameworks (ADFs) are a powerful generalization of abstract argumentation frameworks (AFs). While AFs use directed graphs to represent arguments and attacks, ADFs use acceptance conditions (logical formulas) to specify when an argument is accepted. This allows for more complex relationships like support and collective attacks. However, a key aspect of dialectics – the procedural nature of arguments and counter-arguments – is often lost in the semantic evaluation of ADFs, which typically focuses on the final, static acceptable models. The paper aims to bridge this gap by introducing a notion of "initial models" and "serialisability" that captures this procedural aspect within the semantics of ADFs.
Methods
The authors build upon the characteristic operator-based semantics for ADFs. They define initial models as minimal, non-empty, admissible three-valued models. This is analogous to "initial sets" in AFs, which represent minimal solutions to atomic conflicts.
The core contribution is the generalization of serialisability to ADFs. This concept, previously applied to AFs, describes how extensions can be constructed iteratively from initial sets. For ADFs, serialisability is defined using serialisation sequences, which are sequences of initial models derived from progressively reduced ADFs. The authors introduce a new definition of the v-reduct of an ADF, which captures the unresolved part of the framework after a model v has been applied. This allows them to define serialisation sequences as sequences of initial models of these reducts.
They then use these serialisation sequences to characterize various ADF semantics, including admissible, complete, preferred, grounded, and two-valued models. This provides a procedural interpretation for these semantics, making explicit the step-by-step reasoning process.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Initial Models as Minimal Conflict Resolvers: The definition of initial models for ADFs directly captures the idea of resolving atomic conflicts in a minimal way, mirroring the intuition behind initial sets in AFs.
- Serialisability Brings Procedurality to ADF Semantics: By defining serialisation sequences, the paper injects the dynamic, step-by-step nature of dialectics into the static semantics of ADFs. This is a significant step towards making ADF semantics more interpretable and aligned with their dialectical inspiration.
- Fine-Grained Explanations: Serialisation sequences for ADFs are more expressive than those for AFs. They can explicitly represent both accepted and rejected arguments at each step, offering a richer explanation of how an admissible model is reached.
- Complexity Surprise: The computational complexity of tasks related to initial models in ADFs turns out to be surprisingly higher than for admissible models, suggesting that capturing this minimal conflict resolution aspect comes at a computational cost.
Key Results
- The paper formally defines initial models for ADFs and shows they generalize initial sets from AFs.
- They introduce and analyze serialisability and serialisation sequences for ADFs.
- Most admissibility-based semantics for ADFs (admissible, complete, preferred, grounded, two-valued) are characterized using these serialisation sequences.
- Computational complexity results are provided for tasks related to initial models, showing they are generally harder than corresponding tasks for admissible models. For instance,
EXISTS_isandEXISTS_is*are Σ-complete, andCRED_isis E-complete.
Limitations and Future Work
- Stable Semantics Characterization: The paper notes that their current definition of reducts and serialisation sequences does not directly characterize the stable semantics of ADFs as defined in [Brewka et al., 2013]. This is due to the handling of self-supporting arguments, and identifying and filtering models that require self-support remains an open question.
- Complexity of
VER_is: The exact complexity of theVER_istask (deciding if a given model is an initial model) is left as an open problem. - Future Directions: The authors suggest further research into the relationship between serialisability and approximation fixpoint theory for ADF semantics. They also mention exploring other semantics like strongly admissible semantics and developing algorithms for computing initial sets, potentially by leveraging work on splitting ADFs.
Summary updated