Notes taken from ‘Computing Argumentation in Logic Programming’, by Antonio C. Kakas and Francesca Toni (1999)
1, Introduction
In the argumentation-based approach to the semantics of LP, a logic program P is seen as a theory in a background monotonic logic (the logic of Horn clauses) that can be extended by suitable subsets, delta, of a given set of 'hypotheses' H consisting of all negative (variable-free) literals of the form 'not p' that can be constructed in the language of P. A set of hypotheses delta can be seen as an 'argument' supporting the consequences of the extended theory 'P U delta' derived in the underlying monotonic logic, where the (negative) hypotheses in delta are understood as (ground) atomic facts. In general, not all subsets of H are suitable to extend P. For example, a subset delta may be 'self-conflicting', in the sense that 'P U delta' entails an atom p, with 'not p' in delta. More interestingly, two different sets of hypotheses (or arguments) delta and delta' can be 'conflicting' with each other with only one of them forming an 'allowed extension' of P.
The various (logic programming) LP semantics can be understood via different criteria for selecting appropriate subsets of (hypotheses) H to provide allowed extensions of a logic program (P). These different criteria can all be defined in terms of a common notion of ‘attack’ between subsets of H... The different selection criteria are then based upon comparing candidate sets of hypotheses with attacking sets of hypotheses...
2, Argumentation semantics for logic programming
2.1, A set of hypotheses A attacks another set delta (on an hypothesis not p) iff ‘P U A’ |= p for some not p in delta.
2.3, A set of hypotheses delta is admissible iff for all sets of hypotheses A, if A attacks delta, then delta attacks ‘A – delta’.
Intuitively, delta is admissible iff delta defends itself against each attack A. Note that a set of hypotheses that attacks itself cannot be admissible, because there is no attack against the empty set.
… every admissible set of hypotheses is ‘contained’ in some preferred extension, and thus, in order to determine whether a given query holds with respect to the preferred extension and partial stable model semantics, it is sufficient to determine whether the query holds with respect to the semantics of admissible sets.
… a program may admit several admissible (and preferred) sets of hypotheses which may be incompatible with each other. Any proof theory for the admissibility/preferred extension semantics would therefore need to allow a non-deterministic choice among such sets.
… the construction of an admissible set delta can be done incrementally, starting from a given set of hypotheses delta0, by adding to delta0 suitable defences for it. The existence of several admissible (and preferred) sets of hypotheses reflects itself on the existence of several suitable defences for a given delta0 and imposes a non-deterministic choice among defences in the proof theory.
2.8, A set of hypotheses delta is weakly stable iff for all sets of hypotheses A, if A attacks delta, then ‘delta U A’ attacks ‘A – delta’.
Intuitively, the attack A against delta can be used in conjunction with delta to defend delta against A. Note that, similarly to the case of admissible sets, a set of hypotheses that attacks itself cannot be weakly stable.
Trivially, every admissible set of hypotheses is weakly stable, but not vice versa…
As for admissibility and preferred extension semantics, it can be proved that every weakly stable set of hypotheses is ‘contained’ in some stable theory…
2.9, A set of hypotheses delta is acceptable to another set of hypotheses delta0 iff for all sets of hypotheses A, if A attacks ‘delta – delta0’, then there exists a set of hypotheses D such that D attacks ‘A – (delta0 U delta)’ and D is acceptable to ‘A U delta0 U delta’.
A set of hypotheses is acceptable iff it is acceptable to the empty set of hypotheses.
The base case for the above recursive definition is given by
(BC1) a set of hypotheses delta is acceptable to another set delta0 if there exists no set of hypotheses A attacking (delta – delta0).
… (BC2) delta is acceptable to delta0 if delta is a subset of delta0.
Note that a set of hypotheses delta that attacks itself cannot be acceptable, because there is no attack against the empty set.
Weakly stable and admissible sets of hypotheses are acceptable.
2.13, A set of hypotheses delta is wf-acceptable iff for all sets of hypotheses A, if A attacks delta, then there exists a set of hypotheses D such that D attacks A and D is wf-acceptable.
The base case for wf-acceptability is given by:
(BC) delta is wf-acceptable if no set of hypotheses attacks delta.
(Lemma 2.15) A set of hypotheses delta is wf-acceptable iff each set of hypotheses delta’ (that is a subset of delta) is wf-acceptable.
Complete sets of hypotheses: Sets of hypotheses that are admissible and contain every hypothesis they ‘defend’.
2.16, A set of hypotheses delta is stable iff delta does not attack itself and delta attacks each hypothesis not in delta.
No comments:
Post a Comment