Constrained Assumption-Based Argumentation Frameworks

1. Problem Statement

Assumption-Based Argumentation (ABA) is a well-established framework for structured argumentation where arguments are deductions supported by rules and assumptions, and attacks occur when an argument's claim contradicts an assumption supporting another argument.

The core limitation addressed in this paper is the representational restriction of standard ABA. In standard ABA (particularly in its logic programming instance), arguments and attacks must be built from ground (variable-free) propositional atoms.

• The Issue: Many real-world domains (e.g., legal reasoning, healthcare, planning) involve infinite domains or continuous variables (e.g., income levels, time intervals). To apply standard ABA to these domains, one must "ground" the framework by instantiating all variables with specific values.
• The Consequence: If the domain is infinite (e.g., all possible income values), grounding results in an infinite set of arguments and attacks, making computation infeasible or impossible. Existing non-ground approaches (like argument schemes) often lack formal semantics or cannot integrate constraint solvers effectively.

2. Methodology: Constrained ABA (CABA)

The authors propose Constrained Assumption-Based Argumentation (CABA), a novel framework that lifts the ground restriction by integrating Constraint Logic Programming (CLP) concepts into ABA.

Key Components of CABA

A CABA framework is defined as a 6-tuple $\langle L_c, C, R, CT, A, \overline{\cdot} \rangle$:

1. $L_c$ (Atomic Language): Contains atoms that may include variables.
2. $C$ (Constraints): A set of atomic constraints (e.g., $x > 0$, $x \leq 100$) over a specific domain.
3. $R$ (Rules): Inference rules of the form $s_0 \leftarrow s_1, \dots, s_m$, where the body can contain both atoms and constraints.
4. $CT$ (Constraint Theory): A first-order theory (e.g., Linear Rational Arithmetic) that defines the validity of constraints.
5. $A$ (Assumptions): A set of assumptions (which can contain variables).
6. $\overline{\cdot}$ (Contrary Mapping): Maps assumptions to their contraries.

Core Concepts

• Constrained Arguments: Instead of a single ground deduction, a constrained argument is a tree where leaves are assumptions or constraints. The argument represents a possibly infinite set of ground instances obtained by satisfying the constraints.
  • Tight Constrained Arguments: Arguments where the constraints are minimal and consistent.
  • Most General Constrained Arguments (MGCArg): Arguments with the most general form (using variables) from which all other instances can be derived.
• Attacks: The paper distinguishes between two types of attacks based on the logical relationship between the constraints of the attacking and attacked arguments:
  • Full Attack: The constraints of the attacker logically imply the negation of the constraints of the attacked argument (under the constraint theory).
  • Partial Attack: The constraints of the attacker and the attacked argument are consistent (i.e., there exists at least one ground instance where both hold), but the attacker's claim contradicts an assumption in the attacked argument.
• Semantics: The authors define conflict-free, admissible, and stable extensions directly on the set of constrained arguments, avoiding the need to generate the full ground set.

3. Key Contributions

1. Formal Definition of CABA: The paper introduces the first formal framework for ABA that natively supports variables and constraints, allowing reasoning over infinite domains without explicit grounding.
2. Non-Ground Semantics: It defines semantics (extensions) for CABA using constrained arguments and constrained attacks.
   • It introduces the concept of instance-disjoint and non-overlapping sets of arguments to handle the complexity of variable interactions.
   • It proposes an Argument Splitting procedure that transforms a set of constrained arguments into an equivalent, finite, instance-disjoint, and non-overlapping set, enabling the computation of extensions even when the ground counterpart is infinite.
3. Conservative Generalization: The authors prove that CABA is a conservative generalization of standard ABA. If a CABA framework has no constraints (or finite domains), its semantics reduce exactly to standard ABA semantics via grounding.
4. Theoretical Correspondence:
   • Grounding Correspondence: They establish a rigorous mapping between constrained arguments and their ground instances in standard ABA.
   • Attack Correspondence: They prove that full/partial attacks in CABA correspond to standard attacks in the grounded ABA framework.
5. Proofs: As an extended version, the paper provides a comprehensive appendix with proofs for all theorems, propositions, and lemmas, ensuring the mathematical soundness of the framework.

4. Results

• Theoretical Soundness: The paper demonstrates that the new non-ground semantics are sound with respect to the grounded semantics. Specifically, a set of constrained arguments is a stable extension in CABA if and only if the set of its ground instances is a stable extension in the grounded ABA framework.
• Computational Feasibility: Through the Argument Splitting procedure, the authors show that it is possible to construct finite non-ground extensions for CABA frameworks, even when the corresponding ground extensions are infinite.
  • Example: In a tax reasoning scenario (Example 1.1), CABA can determine that a person must pay tax if income $> 16,000$ without enumerating every possible income value.
• Equivalence Relations: The paper defines an equivalence relation ($\equiv$) over sets of constrained arguments, allowing for the manipulation of argument sets (e.g., splitting, renaming) while preserving their semantic meaning regarding ground instances.

5. Significance

• Bridging Logic Programming and Argumentation: CABA successfully integrates the declarative power of Constraint Logic Programming (CLP) with the structured reasoning of ABA. This allows for the application of ABA in domains where data is continuous or unbounded.
• Scalability: By avoiding the "grounding explosion," CABA makes argumentation applicable to large-scale or infinite-domain problems (e.g., legal compliance with continuous financial thresholds, medical guidelines with variable dosages) that were previously intractable with standard ABA.
• Unified Framework: It provides a unified theoretical basis for analyzing constraints within argumentation, moving beyond specific procedural implementations (like s(CASP)) to a declarative, extension-based semantics.
• Future Directions: The work opens avenues for applying CABA in legal reasoning, planning, and causal discovery, and suggests future research into other semantics (e.g., preferred, grounded) and computational complexity analysis.

In summary, this paper solves the scalability and representational limitations of standard ABA by introducing a constraint-based framework that maintains rigorous semantic definitions while enabling reasoning over infinite domains through symbolic, non-ground representations.