On the Equivalence between Assumption-Based Argumentation and Logic Programming (Extended Abstract)

1 Introduction

Assumption-Based Argumentation (ABA) [Bondarenko et al., 1997; Dung et al., 2009; Toni, 2014] has become one of the leading approaches for formal argumentation. It provides methods for the construction of arguments from given inference rules and defeasible information, called assumptions, as well as for the identification of attacks between assumptions based on the notions of arguments and contraries of assumptions. The semantics of an ABA framework can be given in terms of assumption labellings [Schulz and Toni, 2014; 2017], which assign to each assumption a label IN, OUT or UNDEC.

ABA has a well-studied relationship to abstract argumentation (AA) [Dung, 1995], where arguments and attacks between them are given rather than constructed from knowledge and semantics can be defined in terms of sets of argument labellings [Caminada and Gabbay, 2009], in that both flat ABA is an instance of AA [Dung et al., 2007; Toni, 2014; Caminada et al., 2015] and AA is an instance of flat ABA [Toni, 2012] under many well-studied semantics.

In addition to its relationship with AA, it has been shown that ABA is powerful enough to capture various nonmonotonic reasoning formalisms such as default logic, circumscription, autoepistemic logic, and - most importantly for this paper - logic programming (LP) [Bondarenko et al., 1997; Toni, 2007; 2008; Schulz and Toni, 2015]. More precisely, the aforementioned formalisms can be translated into ABA frameworks in such a way that the semantics of the resulting ABA framework and of the respective formalism correspond.

∗This paper is an extended abstract of an article in the Journal of Artificial Intelligence Research [Caminada and Schulz, 2017].

In our work, we investigate the opposite direction. That is, we define a translation from a (flat) ABA framework to an associated logic program and show that LP is powerful enough to capture the commonly used semantics of (flat) ABA. We here give the main idea of this work, using a number of running examples for illustration, and refer to the full paper [Caminada and Schulz, 2017] for details.

2 Assumption-Based Argumentation

An ABA framework F = 〈L,R,A,¯〉 [Toni, 2014; Bondarenko et al., 1997] consists of a set of inference rules R, based on a formal language L. An important part of this formal language is the set of assumptions A ⊆ L. An assumption represents a defeasible piece of information that is assumed to be true by default, unless contrary information is available. Thus, each assumption is associated (through the function ¯) with an element of the formal language L that is called its contrary.

As an example, consider the ABA framework Fex with the set of assumptions A = {β, γ, δ, ϵ, ϕ}, inference rules

and contraries

Based on an ABA framework, one can start to construct arguments. These are basically derivations that use the rules of the ABA framework together with the set of assumptions to infer a conclusion. An argument is denoted Asm ⊢ x, where Asm is the set of all assumptions used in the derivation and x is the conclusion, i.e. the head of the sentence obtained in the last derivation step. For instance, in the above example Fex, one can construct the following arguments: ∅ ⊢ a (applying rule a ←), {γ} ⊢ b (applying rule b ← γ), {β} ⊢ c (applying rule c ← β), {γ, ϕ} ⊢ d (applying rule d ← γ, ϕ), {δ} ⊢ e (applying rules a ← and e ← a, δ) and {ϵ} ⊢ f (applying rules a ← and f ← a, ϵ). Apart from the arguments that are constructed using the inference rules, there are also "trivial" arguments that consist of a single assumption. In the example above, these are {β} ⊢ β, {γ} ⊢ γ, {δ} ⊢ δ, {ϵ} ⊢ ϵ and {ϕ} ⊢ ϕ.

The semantics of an ABA framework can be provided using assumption labellings [Schulz and Toni, 2014; 2017]. In essence, the idea is to label each assumption in A with IN, OUT or UNDEC. An assumption labelling is called a complete assumption labelling iff for each assumption χ ∈ A it holds that:

• if χ is labelled IN then each ABA argument for conclusion ¯χ has at least one assumption that is labelled OUT
• if χ is labelled OUT then there exists an ABA argument for conclusion ¯χ that has all its assumptions labelled IN
• if χ is labelled UNDEC then there exists an ABA argument for conclusion ¯χ without any assumption labelled OUT and there does not exist an ABA argument for conclusion ¯χ that has all its assumptions labelled IN

Given a (complete) assumption labelling Lab, we write IN(Lab) for the set of assumptions labelled IN, OUT(Lab) for the set of assumptions labelled OUT, and UNDEC(Lab) for the set of assumptions labelled UNDEC. We will sometimes write a (complete) assumption labelling Lab as a triplet (IN(Lab), OUT(Lab), UNDEC(Lab)).

In the above example of ABA framework Fex, there are three complete assumption labellings: Lab1 = ({γ}, {β}, {δ, ϵ, ϕ}), Lab2 = ({β, δ, ϕ}, {γ, ϵ}, ∅}) and Lab3 = (∅, ∅, {β, γ, δ, ϵ, ϕ}).

A complete assumption labelling Lab of an ABA framework F is called:

• a preferred assumption labelling if IN(Lab) is maximal (w.r.t. ⊆) among all complete assumption labellings of F
• a grounded assumption labelling if IN(Lab) is minimal (w.r.t. ⊆) among all complete assumption labellings of F
• a semi-stable assumption labelling if UNDEC(Lab) is minimal (w.r.t. ⊆) among all complete assumption labellings of F
• a stable assumption labelling if UNDEC(Lab) = ∅
• an ideal assumption labelling if IN(Lab) is maximal (w.r.t. ⊆) among all complete assumption labellings of F satisfying that for each preferred assumption labelling Labpref of F, IN(Lab) ⊆ IN(Labpref)

In the example of Fex, Lab1 is a preferred assumption labelling, Lab2 is a preferred, semi-stable and stable assumption labelling, and Lab3 is a grounded and ideal assumption labelling.

3 FromABA to LP

Given an ABA framework F, it is possible to define an associated (normal) logic program PF by replacing each assumption χ in a rule by its negated (using negation-as-failure) contrary, i.e. by not ¯χ. As an example, when doing this for the ABA framework Fex, the result is the following logic program PFex .

a ← b ← not c c ← not b d ← not c, not f e ← a, not d f ← a, not e

Given a logic program P, different semantics can be defined. For current purposes, we apply the concept of a 3valued interpretation 〈T, F 〉 where T and F are subsets of the atoms occurring in the logic program, with T ∩F = ∅. Given a logic program P and a 3-valued interpretation 〈T, F〉, one can define the reduced logic program P 〈T,F〉 by replacing each occurrence of not x by TRUE if x ∈ F, by FALSE if x ∈ T and by UNDEFINED otherwise. The resulting logic program P 〈T,F〉 does not contain any negation-as-failure, so it has a unique minimal 3-valued model [Przymusinski, 1990]. If this unique minimal 3-valued model is equal to 〈T, F 〉, then 〈T, F 〉 is said to be a 3-valued stable model of P [Przymusinski, 1990].

As an example, the logic program PFex has three 3valued stable models: Mod1 = 〈{a, b}, {c}〉, Mod2 = 〈{a, c, e}, {b, f, d}〉 and Mod3 = 〈{a}, ∅〉. To verify that for instance Mod1 is a 3-valued stable model of PFex , we observe that P 〈{a,b},{c}〉 Fex is as follows.

a ← b ← TRUE c ← FALSE d ← TRUE, UNDEFINED e ← a, UNDEFINED f ← a, UNDEFINED

This logic program has the unique minimal 3-valued model 〈{a, b}, {c}〉 which is equal to Mod1, hence Mod1 is a 3valued stable model of PFex . In a similar way, it can be verified that alsoMod2 andMod3 are 3-valued stable models of PFex .

A 3-valued stable model Mod = 〈T, F 〉 of logic program P is called:

• a regular model if T is maximal (w.r.t. ⊆) among all 3-valued stable models of P
• a well-founded model if T is minimal (w.r.t. ⊆) among all 3-valued stable models of P
• an L-stable model if T ∪F is maximal (w.r.t. ⊆) among all 3-valued stable models of P
• a (2-valued) stable model if T ∪ F consists of all the atoms in P
• an ideal model if T is maximal (w.r.t. ⊆) among all 3valued stable models of P satisfying that for each regular model 〈Treg, Freg〉 of P , T ⊆ Treg

In the example of Pex, Mod1 is a regular model, Mod2 is a regular, L-stable and (2-valued) stable model, andMod3 is a well-founded and ideal model.

One of our main findings is that it is possible convert an assumption labelling Lab of an ABA framework F to a 3valued stable model Mod of the associated logic program PF, and vice versa.

To convert an assumption labelling to a 3-valued interpretation, we start by "inverting" the labelling. That is, we construct an interpretation 〈T ′ , F ′ 〉 where T ′ contains the contraries of the assumptions that are OUT, whereas F ′ contains the contraries of the assumptions that are IN (with the additional condition that each of these contraries actually occurs in PF ). However, since we started with assumptions, this will only yield the status of atoms which are contraries of assumptions. In order to obtain the status of all atoms in the logic program (including those that are not the contrary of any assumption in the ABA framework) we perform a simple trick: apply the reduct. That is, we define Lab2Mod(Lab) (the function that converts a labelling Lab of F into a 3-valued stable model Mod of PF ) as the unique minimal model of P 〈T ′ ,F ′ 〉 F .

As an example, consider again Fex, which (as we have seen before) has the complete assumption labellings:

It holds that

• Lab2Mod(Lab1) = 〈{a, b}, {c}〉 =Mod1 (with 〈T ′ , F ′ 〉 = 〈{b}, {c}〉),
• Lab2Mod(Lab2) = 〈{a, c, e}, {b, f, d}〉 =Mod2 (with 〈T ′ , F ′ 〉 = 〈{c, e}, {b, f, d}〉), and
• Lab2Mod(Lab3) = 〈{a}, ∅〉 =Mod3 (with 〈T ′ , F ′ 〉 = 〈∅, ∅〉).

In this example, the application of the reduct and minimal model thereof adds atom a as a true atom to each interpretation 〈T ′ , F ′ 〉.

It is also possible to go the other way around. That is, given a 3-valued stable model Mod of PF , one can define the associated complete assumption labelling Lab of F, using a function called Mod2Lab. The idea is that:

• the assumptions whose contrary is in F are labelled IN
• the assumptions whose contrary is in T are labelled OUT
• the assumptions whose contrary does occur in PF but neither in T or F are labelled UNDEC
• the assumptions whose contrary does not even occur in PF are labelled IN as well

As an example, for F and PF it can be observed that Mod2Lab(Mod1) = Lab1, Mod2Lab(Mod2) = Lab2 and Mod2Lab(Mod3) = (Lab3).

We have proven that when the domain of Lab2Mod consists of the complete assumption labellings of F, and the domain of Mod2Lab consists of the 3-valued stable models of PF, Lab2Mod and Mod2Lab are bijective functions that are each other's inverse. Moreover,

1. when Lab is a preferred assumption labelling of F, Lab2Mod(Lab) is a regular model of PF, and when Mod is a regular model of PF, Mod2Lab(Mod) is a preferred assumption labelling of F;
2. when Lab is a stable assumption labelling of F, Lab2Mod(Lab) is a (2-valued) stable model of PF, and when Mod is a (2-valued) stable model of PF, Mod2Lab(Mod) is a stable assumption labelling of F;
3. when Lab is a grounded assumption labelling of F, Lab2Mod(Lab) is a well-founded model of PF, and when Mod is a well-founded model of PF, Mod2Lab(Mod) is a grounded assumption labelling of F;
4. when Lab is an ideal assumption labelling of F, Lab2Mod(Lab) is an ideal model of PF , and when Mod is an ideal model of PF, Mod2Lab(Mod) is an ideal assumption labelling of F.

Overall, the results regarding formal correspondences between assumption labellings and logic programming models are summed up in Table 1.

4 Limitations

For our translation from ABA to LP to work, there need to be a few restrictions on the ABA framework. The first restriction is that the ABA framework should be flat [Toni, 2013]. This means that no assumption appears in the head of an ABA rule. This is important, for if the head of an ABA rule was an assumption, the resulting LP rule would have negation-asfailure in its head, so the result would not be a normal logic program.

The second restriction is that each assumption should have just a single contrary, rather than a set of contraries. This restriction is shared by most of the ABA literature (like [Bondarenko et al., 1997; Dung et al., 2009; 2007; Toni, 2014; Schulz and Toni, 2014]), although some works on ABA (like [Gaertner and Toni, 2007; 2008; Fan and Toni, 2014; 2015]) allow an assumption to have more than one contrary. Our current translation from ABA to LP would not be welldefined in the latter case.

The third restriction is that the contrary of an assumption should not be an assumption itself. Although this restriction is not required for the well-definedness of the resulting logic program, examples exist where violating this restriction results in breaking the link between the assumption labellings of the ABA framework and the logic programming models of the associated logic program.

For the second and third restriction, workarounds exist. For instance, it is possible to convert an ABA framework where assumptions have multiple contraries to an equivalent ABA framework 1 where each assumption has a single contrary [Gaertner and Toni, 2008]. Furthermore, it is possible to convert an ABA framework where the contrary of an assumption may be an assumption to an equivalent ABA framework where this is not the case. Details of the respective translations can be found in the full paper. For an ABA framework that does not comply with the second or third restriction, the workaround idea is to first translate it to an equivalent ABA framework that does comply with the restriction, and then translate this to the associated logic program. The logic programming models (2-valued) stable, well-founded and ideal semantics, respectively) of this logic program will coincide with the assumption labellings of the original ABA framework as previously described.

1 With an equivalent ABA framework we mean an ABA framework that has the same complete (resp. preferred, semi-stable, stable, grounded and ideal) assumption labellings.

Another type of restriction is regarding the semantics applied to the ABA framework. Although our translation works for complete, preferred, stable, grounded and ideal assumption labellings (which coincide with the 3-valued stable, regular, (2-valued) stable, well-founded and ideal models, respectively, of the associated logic program through the functions Lab2Mod and Mod2Lab) it is not the case that the semistable assumption labellings of an ABA framework coincide with the L-stable models of the associated logic program. However, it can be observed that semi-stable assumption labellings do coincide with L-stable models when the ABA framework is assumption-spanning, that is, when each nonassumption in the language is the contrary of an assumption.

5 FromLP to ABA

Apart from the translation from ABA to LP, it is also possible to translate from LP to ABA, as investigated in previous work [Bondarenko et al., 1997; Schulz and Toni, 2015; 2016]. The idea is that, given a logic program, one can translate it to an ABA framework by replacing each occurrence of not x by an assumption not x. 2 For instance, for the logic program Pex mentioned above, the corresponding ABA framework is as follows,

with the set of assumptions in the underlying language being {not a, not b, not c, not d, not e, not f}. Note that the assumption not a does not occur in any of the ABA rules.

We observe that when translating a logic program to an ABA framework and then back to a logic program, the final logic program is precisely the same as the one at the start. This makes it possible to reuse part of our existing technical results from the "ABA to LP" direction to apply to the "LP to ABA" direction (see the full paper for details). In particular, it turns out that the various types of models of a logic program P coincide (through the functions Mod2Lab and Lab2Mod) with the various types of assumption labellings of the associated ABA framework FP , thus generalising existing work [Bondarenko et al., 1997; Schulz and Toni, 2015; 2016]. An overview of the semantic correspondence is provided in Table 2.

2 Apart from that, the resulting ABA framework has an assumption not x ∈ A (with not x = x) for each atom x occurring in the logic program, even in cases when not x itself does not occur in any of the ABA inference rules in R. This makes sure that the resulting ABA framework is assumption-spanning

As indicated in Table 2, for the "LP to ABA" direction, we do obtain equivalence between L-stable models and semistable assumption labellings (which is not the case for the "ABA to LP" direction, see Table 1). This is because translating a logic program results in an ABA framework that is assumption-spanning.

6 Discussion

In this work we re-examined the relationship between ABA and LP and found that the most frequently studied fragment of ABA, namely flat ABA frameworks, does not only subsume normal logic programming as previously shown [Bondarenko et al., 1997; Toni, 2007; 2008; Schulz and Toni, 2015], but is in fact also itself subsumed by normal logic programming through a straightforward translation. That is, flat ABA can be seen as LP with a slightly different syntax since the outcome that is yielded by a flat ABA framework under common ABA semantics (that is: complete, grounded, preferred, stable and ideal) is essentially the same as the outcome yielded by its (syntactically nearly identical) associated normal logic program under common LP semantics, and vice versa. The difference is that in ABA the outcome is defined in terms of assumptions (which correspond to negation-asfailure atoms in the associated logic program) whereas in LP the outcome is defined in terms of atoms in the logic program. However, since in LP the status of the atoms is determined solely by the status of the negation-as-failure atoms, flat ABA and normal LP are semantically equivalent. As a by-product of our work, we prove that the ideal semantics for ABA is not just inspired by, but coincides with, the ideal scenario semantics for LP [Alferes et al., 1993].

ABA methods have already been successfully applied to LP, e.g. for explaining [Schulz and Toni, 2016] as well as visualizing [Schulz, 2015] logic programs under certain semantics. Our results pave the way for the application of LP methods to (flat) ABA frameworks, since our translation prevents an exponential blow-up while preserving the semantics. Efficient computation methods for LP semantics [Janhunen et al., 2006; Gebser et al., 2011] could for instance be used to determine the semantics of ABA frameworks, which is a promising direction for future work.