Refinement of gluing proofs and refutations

The Ijcai 2007 paper gives the following algorithm for computing all preferreds and stables:

Step 0: Find all proofs and refutations of all arguments.
Step 1: Find the set DA of all credulously ambiguous arguments.
Step 2: Choose a labeling (J, D) of DA in which all elements of DA are labeled (the 'disambiguation').
Step 4: If, for all elements of DA, there exists a proof or a refutation option that is compatible with (J, D), then goto Step 5, else goto Step 6.
Step 5: Collect all proof and refutation options compatible with (J, D). Output their union as a preferred extension. When it has no unlabeled arguments, output it as a stable extension.
Step 6: Choose the next disambiguation and goto Step 4. If none exists, stop.

A refinement is needed, as follows.

This algorithm gives all stable extensions, but leads to a special class of preferred extensions, namely the globally disambiguating ones. A set of arguments is _globally disambiguating_ if each argument that is dialectically ambiguous is either in it or attacked by it. Stable extensions are globally disambiguating, but there exist preferred extensions that are not globally disambiguating:

#Baroni and Giacomin, Fig. 3 (CMNA 2004)
a b d, b c f, c a, d e, e d, f g, g f

In this example, the partial disambiguating choice e+ g+ cannot be extended to a global disambiguation, since the ambiguity of a, b and c cannot be resolved in a preferred extension containing e and g (of which there is only one, namely the set {e, g}).

Excluding step 4 gives all preferred extensions (and hence all stable extensions). But now some non-preferreds are given too. Example: a b, b a, c d, d c gives also a (b) etc as output, namely as the result of gluing everything compatible with the global disambiguation a+ b- c+ d+ (and also a+ b- c- d-).

We need a check to ensure that only preferreds are produced. That check occurs in Step 5' below.

Step 0: Find all proofs and refutations of all arguments.
Step 1: Find the set DA of all credulously ambiguous arguments.
Step 2: Choose a labeling (Jd, Dd) of DA in which all elements of DA are labeled (the 'disambiguation').
Step 5: Collect all proof and refutation options compatible with (Jd, Dd). Glue them into one labeling (J, D). ((Jd, Dd) need not be a sublabeling of (J, D).)
Step 5': Check whether there is a dialectically ambiguous argument unlabeled in (J, D) that has a proof or a refutation that is compatible with (J, D). If so, goto step 6 (i.e., skip this labeling). If not, output (J, D) as a preferred extension.
Step 5'': If (J, D) has no unlabeled arguments, output (J, D) as a preferred extension (if it has not been output before).
Step 6: Choose the next disambiguation and goto Step 4. If none exists, stop.

This version of the algorithm is implemented in version 0.93 of the tool.

Bart Verheij's home page - research - publications