TL;DR
This paper introduces Featured Argumentation Frameworks (FAF) and Extended FAF (EFAF), which enrich abstract argumentation by incorporating features associated with arguments. This allows for more nuanced knowledge representation and reasoning, particularly in scenarios where constraints on argument features are crucial, leading to a more expressive and complex computational landscape.
What Problem Does This Paper Address?
Formal argumentation, as pioneered by Dung, provides a powerful abstract model for representing disputes. However, this abstraction often loses valuable information about the arguments themselves, such as their content, origin, or associated metadata. This limitation hinders its application in real-world scenarios where such features are critical for decision-making. The paper addresses this by proposing FAF and EFAF, which integrate argument features and allow reasoning over constrained sub-frameworks, thereby bridging the gap between abstract argumentation and richer, feature-aware knowledge representation.
Methods
The core contribution is the introduction of two novel frameworks:
- Featured Argumentation Framework (FAF): This extends Dung's abstract argumentation framework (AF) by associating each argument with a set of features. These features are represented using unary and binary facts (e.g.,
author(argument_id, author_name)orterm(argument_id, policy_term)). Queries in FAF are expressed using conjunctive relational calculus, evaluated over the extensions of the underlying AF. - Extended FAF (EFAF): This further enhances FAF by incorporating a first-order logic (FOL) formula. This formula acts as a constraint to select "feasible" subframeworks that minimally differ from the original FAF. These subframeworks are derived by deleting a minimal set or number of arguments and attacks, ensuring the FOL constraint is satisfied. This allows for reasoning about specific scenarios or contexts defined by these constraints.
The paper also investigates the computational complexity of verification and acceptance problems for these new frameworks, comparing them to existing ones like incomplete AF (iAF).
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Argument Features Enhance Expressiveness: By associating arguments with features, FAF and EFAF move beyond purely structural relationships (attacks) to incorporate semantic information, enabling more sophisticated reasoning.
- Subframeworks as "Possible Worlds": EFAF's concept of subframeworks, derived by minimally modifying the original framework to satisfy FOL constraints, can be viewed as representing different "possible worlds" or scenarios. This allows for reasoning about what holds true in specific, constrained contexts.
- Complexity Trade-offs: While FAF's acceptance problem complexity remains similar to AF, EFAF introduces significantly higher computational complexity for verification and acceptance problems, especially when dealing with set-based subframework semantics. This highlights the expressive power gained at the cost of computational tractability.
- EFAF as a Unifying Framework: The paper demonstrates that existing frameworks like incomplete AF (iAF), correlated iAF, and constrained iAF can be viewed as special cases of EFAF, suggesting EFAF's potential as a general formalism for representing and reasoning about various argumentation scenarios.
Key Results
- FAF Complexity: The complexity of acceptance problems in FAF does not increase compared to standard AF.
- EFAF Complexity: Verification and acceptance problems in EFAF are generally harder than in iAF and constrained iAF. For instance, verification problems for EFAF are strictly harder than for constrained iAF, except for specific cases where they match.
- EFAF as a Generalization: The paper formally shows that iAF, correlated iAF, and constrained iAF can be rewritten into extensions-equivalent EFAFs, demonstrating EFAF's broader applicability.
- Complexity Tables: The paper provides detailed complexity tables (Table 1 and Table 2) for verification, possible, and necessary credulous/skeptical acceptance problems across various semantics for AF, FAF, iAF, ciAF, and EFAF, offering a comprehensive comparison.
Limitations and Future Work
- Computational Complexity: The increased complexity of EFAF, particularly for verification and acceptance problems, is a significant limitation for practical applications. The paper acknowledges this by providing detailed complexity analyses.
- Future Work: The authors suggest extending the investigation to other argumentation semantics (e.g., semi-stable) and allowing polynomial-time functions within queries and constraints. They also propose exploring the mapping of FAF to database repairs to leverage existing DB technologies for feature management.
Summary updated