A tutorial on assumption-based argumentation

1.Introduction

From the late 1980s, argumentation has emerged in AI as a powerful method for representing a diverse range of knowledge and supporting several kinds of reasoning. Starting with Lin and Shoham (1989), Dung (1991), Kakas, Kowalski, and Toni (1992), Kakas, Kowalski, and Toni (1998) and Bondarenko, Toni, and Kowalski (1993), argumentation was identified as a way for understanding and reconciling differences (as well as point out similarities) of various existing formalisms for non-monotonic, default reasoning as studied in AI (such as default logic (Reiter, 1980) and circumscription (McCarthy, 1980)). This line of research led to the development of two argumentation frameworks: abstract argumentation (AA) (Dung, 1995) and assumption-based argumentation (ABA) (Bondarenko, Dung, Kowalski, & Toni, 1997). Moreover, starting with Pollock (1987), argumentation was identified as a way to understand defeasible reasoning as studied in philosophy, leading, in particular, to DeLP (García & Simari, 2004) and ASPIC+ (Modgil & Prakken, 2013). Furthermore, Krause, Ambler, and Fox (1992), Krause, Ambler, Elvang-Gøransson, and Fox (1995) pointed to an important role for argumentation to support decision-making (in general and in a medical setting), leading to argumentation frameworks such as that of Amgoud and Prade (2009). Finally, Elvang-Gøransson and Hunter (1995) used argumentation for resolving inconsistencies in logic-based reasoning, leading to the argumentation logic of Besnard and Hunter (2008).

This paper provides an introductory tutorial to ABA, while also stressing and exemplifying its use for a wide range of reasoning tasks, including non-monotonic reasoning (for which it was initially proposed), defeasible reasoning, decision-making and reasoning with inconsistent information. The tutorial is meant to serve as a reference manual on ABA and argumentation for students and researchers alike.

ABA is closely related to AA, in that it is an instance thereof while at the same time admitting AA as an instance (see Toni, 2012). However, AA takes as given a set of arguments and an attack relationship between arguments in this set, and focuses on ascertaining which sets of arguments can be deemed to be ‘winning’ (according to a catalogue of different, the so-called- semantics). Instead, in ABA arguments and attacks are derived from given rules in a deductive system, assumptions, and their contraries. However, ABA is abstract too, in the sense that, like AA, it does not commit to any specific instance and admits, instead, several instances (including AA). However, ABA's building blocks (rules, assumptions, contraries) are at a lower level of abstraction than those of AA (arguments and attacks).

ABA is equipped with different semantics for determining ‘winning’ sets of assumptions. The ‘winning’ sets of arguments (à-la-AA) can then be determined from the ‘winning’ sets of assumptions, in a straightforward manner – and the assumption-level and argument-level views are fully equivalent in ABA. Manipulating assumptions directly (and arguments only indirectly) rather than arguments though is advantageous from a computational viewpoint, as it allows to (implicitly) exploit overlappings between arguments and avoid recomputation as well as terminating, even in the presence of loops in the rules, in determining whether a conclusion can be supported by a ‘winning’ set of arguments.

ABA is equipped with a catalogue of computational techniques (Dung, Kowalski, & Toni, 2006; Dung, Mancarella, & Toni, 2007; Toni 2013), which have their foundation in logic programming, and in particular the methods of Eshghi and Kowalski (1989), Dung (1991) and Kakas and Toni (1999). These techniques can be used to determine whether given conclusions can be supported by a ‘winning’ set of arguments. They are in the form of disputes, provably correct w.r.t. the semantics and incorporating various forms of ‘filtering’ for avoiding recomputation. These disputes can be seen as games between (fictional) the proponent and opponent players, and rely upon data structures for representing the state of the game at any given time. They are specified algorithmically in a way that lends itself to principled and provably correct implementations, and indeed several systems exist to support ABA-style argumentation. As a consequence, ABA can be deemed to be a fully computational form of argumentation.

The computational complexity of various reasoning tasks for various instances of ABA and various semantics has been studied e.g. in Dimopoulos, Nebel, and Toni (2002) and Dunne (2009). This topic will not be covered in this tutorial paper.

This paper complements the overview in Dung, Kowalski, and Toni (2009) by being an introductory tutorial, illustrating notions, justifying design choices and discussing (disregarded) alternatives.

The paper is organised as follows. In Section 2, we give a simple illustrative example of argumentation in general and ABA in particular. In Section 3, we describe and discuss ABA frameworks, including rules in a deductive system, assumptions and contraries. In Section 4, we define arguments and attacks in ABA. In Section 5, we give the main semantics for ABA, and in Section 6, we give several examples of ABA. In Section 7, we describe the computational machinery for reasoning in ABA, under two different semantics. In Section 8, we consider several frequently asked questions (FAQs) on ABA. In Section 9, we conclude.

2.A simple illustrative example

You like eating good food, this makes you really happy. But you are very health-conscious too, and do not want to eat without a fork and with dirty hands. You are having a walk with some friends, and your friend Nelly is offering you all a piece of lasagna, looking really delicious. You are not quite sure, but typically you carry no cutlery when you go for walks, and your hands will almost certainly be dirty, even if they may not look so. Should you go for the lasagna, trying to snatch it quickly from the other friends? You may argue with yourself as follows:

The set of arguments {α, β, γ} and the attack relationship between them (that β attacks α, and γ attacks β) form an AA framework (Dung, 1995). All semantics for AA agree with our earlier analysis of what is dialectically justified by sanctioning {α, γ} as ‘winning’ arguments. Similarly, given the initial set of arguments {α, β} and the attack relationship between them that β attacks α, all semantics for AA agree that {β} is ‘winning’.

In this context, ABA provides:

3.ABA frameworks

An ABA framework is a tuple ⟨L,R,A,0¯⟩ where

Language. The language component L of ABA frameworks can be omitted, as it can always be ‘reconstructed’ from the other components (being the set of all sentences occurring in them). The language is not restricted to propositional atoms (as in the earlier Example 3.1) but can be any language of sentences. Different instances of ABA have been studied (Bondarenko et al., 1997), corresponding to existing formalisms for default reasoning, some with a propositional language, some others with a first-order language, and others still with a modal language. For some studied instances of ABA, L is closed under classical negation ¬ (namely if a sentence σ is in L then ¬ σ is as well), whereas for some others it is not. The language may include an implication connective ⊃ and R may include inference rules (e.g. modus ponens for q ⊃ p, namely p ← q ⊃ p, q) to reason with it, as discussed in (Dung et al., 2006). The language for the ABA framework in Example 3.1 includes neither negation nor implication.

Rules. The rules in R may be written using different syntactical conventions, for instance p← q, a may be written as q,ap or q, a↠p, equivalently. These rules may represent domain-independent inference rules and axioms, as well as domain-dependent knowledge/information. ABA's early versions (Bondarenko et al., 1993, 1997) as well as other frameworks for structured argumentation (García & Simari, 2004; Modgil & Prakken, 2013) single out domain-dependent and/or factual knowledge/information as a separate component (a theory T⊆L in early-days-ABA). Any theory T can be equivalently written as part of R as a set of rules with an empty body and is thus omitted in our presentation of ABA here.

Sometimes rules are written in the form of schemata, e.g. p(X) ← q(X), a(X), using variables that are meant to be instantiated over an implicit vocabulary. For example, for vocabulary 1, f(1), f(f(1)), …, the schema p(X) ← q(X), a(X) stands for the (infinite) set of rules

Rules can be chained to derive/deduce conclusions, where

Figure 1.

Deductions {q,a}⊢pR1 (left), {}⊢qR2 (middle) and {a}⊢pR3 (right) for Example 3.1.

Deductions can alternatively be defined in a forward fashion (as in Bondarenko et al. (1997)) or in a backward fashion (as in Dung et al. (2006)). For example, the earlier deduction

Assumptions are simply ‘special’ kinds of sentences in the language, playing the role of the only potential ‘weak’ points in arguments (namely the bits of an argument that can be attacked) and argumentation in ABA amounts to identifying ‘strong’ sets of assumptions. We impose that there needs to be at least one assumption in an ABA framework as otherwise argumentation is trivial – there is no ‘weak’ point to debate about. Note that the (semantics and computational) machinery for ABA works perfectly well in the case in which the set of assumptions is empty, but it equates to reasoning in the deductive system ⟨L,R⟩ and is, thus, uninteresting from an argumentative viewpoint. All instances of ABA that we have studied naturally have a non-empty set of assumptions. As we discuss further in Section 8, it is easy to engineer ABA frameworks that have a non-empty set of assumptions, but if the knowledge/information to be reasoned with requires no assumptions then ABA (or argumentation in general) is definitely an overkill for the problem at hand.

In general, assumptions may be hypothesised to construct arguments (as we will see in Section 4) or derived using R and possibly other assumptions. We say that

Some of the ABA instances that have been studied (Bondarenko et al., 1997) are flat (e.g. the instances corresponding to logic programming and default logic), whereas others are not (e.g. the instance corresponding to auto-epistemic logic). Non-flat ABA frameworks are computationally demanding (Dimopoulos et al., 2002) and indeed all existing computational mechanisms for ABA are defined for flat ABA frameworks. We will focus on flat ABA frameworks.

Contrary. We impose that each assumption has one single contrary sentence (by imposing that 0¯ is a total mapping onto L). Indeed, the contrary of an assumption can be seen as a ‘handle’ to open debate about the assumption, and thus it needs to be clear what this is. We do not impose that the contrary mapping is bijective, so different assumptions can have the same contrary. Note also that contrary is different from negation, for at least two reasons: negation may not even occur in L, and, even if it does, contrary is only given for assumptions, whereas negation may apply to any sentence, not just assumptions. Also, contrary is not required to be symmetric (the contrary of an assumption may not even be an assumption, and even if it is it may not have the original assumption as its contrary). In other words, contrary is a very generic, flexible notion, in the same way that the attack relationship is in AA (Dung, 1995). For specific instances of ABA contrary can of course correspond to negation and be symmetric, but in general these are not requirements (as shown in our earlier Example 3.1, where contrary is not given via negation and is not symmetric).

4.ABA arguments and attacks

In ABA, arguments are deductions of claims using rules and supported by sets of assumptions, and attacks are directed at the assumptions in the support of arguments:

In the case of Example 3.1, the attack relationship is as follows:

We have seen in Section 3 that the tree-style notion of deduction can be defined alternatively in a backward or forward manner. We have (implicitly) used the tree-style notion in the earlier definition of argument, but any of the other notions can be used to give a notion of argument. The different notions of argument thus obtained are equivalent (Dung et al., 2006, 2009, 2010) as follows:

Attacks between arguments correspond in ABA to attacks between sets of assumptions, where

This hybrid notion of attack corresponds to the notions of attack between arguments and between assumptions as follows:

Some existing frameworks for structured argumentation use a notion of sub-argument of an argument. This notion is implicit in ABA (where a sub-argument of an argument is a sub-tree of that argument). However, the notion of sub-argument plays no role in ABA, semantically or computationally, since, by virtue of the correspondences discussed in this section, ABA operates at the level of assumptions.

5.ABA semantics

Argumentation semantics offer declarative methods to determine ‘acceptable’ sets of arguments, namely ‘winning’ sets of arguments from a dialectical viewpoint. In ABA, these semantics can equivalently be used to determine ‘acceptable’/‘winning’ sets of assumptions. Below, we discuss and illustrate both views on argumentation semantics in ABA, as well as their equivalence (Dung et al., 2007, 2009; Toni, 2012 for more details).

Argument-level view. With arguments and attack between arguments defined for ABA, standard semantics for AA (Dung, 1995) can be applied in ABA. Formally, a set of arguments <tt>A</tt> is22

We give below examples showing how the semantics above differ, sanctioning different sets of arguments as ‘acceptable’ or ‘winning’, adapted from Bondarenko et al. (1997) and Dung et al. (2007).

We have seen in Example 5.1 that the ‘credulous’ semantics may also differ in determining which sets of arguments are ‘winning’. This is further illustrated by the following example:

Assumption-level view. ABA is also equipped with notions of ‘acceptability’ of sets of assumptions, mirroring the notions of ‘acceptability’ of sets of arguments but with the notion of attack between (sets of) arguments replaced by the notion of attack between sets of assumptions. Formally, a set of assumptions A is

Equivalently, the notions of admissible and complete sets of assumptions can be defined in terms of the hybrid notion of attack seen in Section 4, where a set of assumptions is

Note that the efficiency of the hybrid view is also afforded by the the argument-level view of semantics. In the case of Example 5.4, {{d} ⊢ d, {b, c} ⊢ r} is admissible (and preferred), with {a} ⊢ p the only argument needing to be counter-attacked.

Correspondence between argument-level and assumption-level views. Directly from the results in (Dung et al., 2007) and (Toni, 2012), the two views over the semantics of ABA are equivalent, in the following sense:

Sentence-level view. Given an ‘acceptable’/‘winning’ set of argument, a sentence can be deemed ‘acceptable’/‘winning’ if it is the claim of an argument in the set. Equivalently, given an ‘acceptable’/‘winning’ set of assumptions, a sentence can be deemed ‘acceptable’/‘winning’ if it is the claim of an argument supported by a set of assumptions contained in the set. An ‘acceptable’/‘winning’ sentence may be a belief held by an agent, an action to be executed by an agent, a joint action by several agents, a decision, etc, depending on the area of application.

Given the arguments and attacks for the ABA frameworks in Examples 3.1 and 5.4, all notions coincide, in that they sanction the same sentences as ‘acceptable’/‘winning’. Thus, in Example 3.1, r is admissible, grounded etc, whereas p is not. For ABA frameworks where the semantics differ, these notions differ too, by sanctioning different sentences as ‘acceptable’/‘winning’. As an illustration, in Example 5.3, c_b is preferred but not stable.

Other observations. All the semantics considered earlier, in terms of sets of arguments or sets of assumptions, can be equivalently reformulated in terms of backward-style and forward-style arguments, by virtue of the correspondence results between the various notions of argument given earlier in Section 4.

6.Some examples

Dung et al. (2009) give examples of use of ABA to model reasoning with argument scheme, decision making, dispute resolution and game-theoretic notions. Furthermore, Matt, Toni, and Vaccari (2010), Matt, Toni, Stournaras, and Dimitrelos (2008), Fan and Toni (2013), Fan, Craven, Singer, Toni, and Williams (2013) give several uses of ABA to model decision-making, for various notions of dominant decisions. This section complements these works by illustrating the use of ABA for default reasoning, defeasible reasoning and persuasion. Note that an ABA framework is a (structured) representation of knowledge/information and of a method for reasoning with it. Given some knowledge/information, several alternative ABA frameworks can be chosen to represent and reason with it. Below, we make some specific choices but others may be suitable too.

Default reasoning. One of the most widely studied examples of default reasoning amounts to reasoning with the following information: typically birds fly (they fly by default), but penguins do not, despite being birds. Given this information, do tweety (a penguin) and joe (a bird) fly? Humans can naturally reason with this information, and answer that tweety does not fly whereas joe does. If the additional information that joe is a penguin is given, humans would withdraw the conclusion that it flies and infer that it does not. This type of reasoning cannot be modelled in classical logic, because it trivialises in the presence of inconsistencies (e.g. that tweety flies, being a bird, and does not fly, being a penguin) and since classical logic is monotonic (and thus it does not allow to withdraw conclusions). This problem can be modelled in ABA by using

Defeasible reasoning. Here we consider a simple example adapted from Dung and Thang (2010), and inspired by a legal setting:

Given this ABA framework, argument {notGuilty(oj)} ⊢ innocent(oj) is attacked by argument {DNAfromReliableEvidence(oj)} ⊢ killer(oj) which is attacked by argument {} ⊢ evidenceUnreliable(oj). Thus innocent(oj) is admissible, grounded, etc, and there is a defeasible inference for innocent(oj).

Persuasion. We model in ABA a variant of an example originally proposed in Sartor (1994) and later used in Prakken and Vreeswijk (2002) and Cayrol, Devred, and Lagasquie-Schiex (2006), presenting a dialogue between two agents a and b, trying to persuade one another:

7.Dispute derivations

Several computational techniques and tools have been defined for ABA (Dung et al., 2006, 2007; Toni, 2013), with the following features:

Data structures. The tuples, for all dispute derivations, include components

In addition, the dispute derivations of Toni (2013), include components

Elements of P, O and Args may be potential (rather than actual) arguments66. Given the ABA framework in Example 3.1, the left-most and middle trees in Figure 2 are potential arguments for p, whereas the right-most tree is an actual argument (namely the argument {a} ⊢ p). Potential arguments may be seen as intermediate steps in the construction of actual arguments or failed attempts to construct actual arguments. For example, the left-most and middle trees above are intermediate steps in the construction of the right-most tree, and, for the ABA framework in Example 3.1, the tree consisting solely of the root s is a potential argument for s, but no actual argument can be obtained from it.

Figure 2.

Potential (left and middle) and actual (right) arguments for Example 3.1.

Algorithmic aspects. The flowchart in Figure 3, adapted from Toni (2013), summarises the rules of the game played by proponent and opponent in dispute derivations for grounded and admissible semantics (the grounded version does not use the parts in bold). We show how to use this flowchart to generate dispute derivations below. First, however, note that dispute derivations are algorithms, and as such have procedural features such as ‘marking’ of assumptions that have already been ‘processed’ in the support of (potential or actual) arguments. We use the notation A ⊢_S σ for an argument with claim σ, where A⊆A is ‘marked’ and S⊆L is not. Thus, in Figure 2, the left-most potential argument is denoted {} ⊢_{p} p, the middle potential argument may be denoted {} ⊢_{{q, a}} p or {a} ⊢_{q} p (depending on whether the assumption a has already been ‘processed’ or not), and the right-most actual argument ({a} ⊢ p in the notation of Section 4) may be denoted {} ⊢_{a} p or {a} ⊢_{} p (again, depending on whether the assumption a has already been ‘processed’ or not). Premises of (actual or potential) arguments are selected from the ‘unmarked’ part.

Figure 3.

Flowchart summarising dispute derivations for admissible and (without the bits in bold) grounded semantics. Labels in square brackets refer to steps of the derivations as defined in Dung et al. (2006, 2007) and Toni (2013) but are solely used here to connect examples to this flowchart. ‘p-arg’ stands for ‘potential argument’, and um(π) stands for ‘unmarked part of p-arg π’. Square boxes without outgoing edges are final steps in one iteration of the algorithm and implicitly link back to the root of the flowchart (rounded diamond), where each iteration starts. Rounded boxes are exit points.

Figure 4 gives a dispute derivation for determining whether d is grounded and admissible,77 given the ABA framework in Example 5.4 (the Args and Att components for this derivation are given separately in Figure 5). This derivation is obtained as follows, using the flowchart in Figure 3.

Figure 4.

A successful dispute derivation for Example 5.4.

Figure 5.

Left: the dialectical tree corresponding to the Args and Att components computed by the dispute derivation of Figure 4: nodes of the tree hold elements of Args and an edge N₁←N₂ in the tree corresponds to an attack in Att between the elements of Args held at N₁ and N₂. Middle: the step in the derivation when the argument and the attack relationship were added to the dialectical tree. Right: the actual argument view of the dialectical tree.

At step 1, P is not empty, so the branch labelled 1 is followed in the flowchart. Since O is empty, it makes sense for P to play next. There is only one p-argument that can be chosen in P (i.e. {} ⊢_{d} d), and only one ‘unmarked’ premise in it (i.e. d). This is an assumption, so branch [1(i)] applies, resulting in an attack against the chosen p-argument (on the selected premise) being added to O (i.e. {} ⊢_{p} p, since d‾=p). The ‘marking’ of d in {} ⊢_{d} d results in {d} ⊢_{} d, and, since this is an actual argument with empty ‘unmarked’ part, it is removed from P and added to the dialectical structure (see Figure 5)88.

A new iteration then starts (step 2). Since P is empty and O is non-empty, branch 2 applies, {} ⊢_{p} p is chosen in O and p is selected in the (non-empty) ‘unmarked’ part of this p-argument (if no premise were left in the ‘unmarked’ part then the derivation would be aborted). Since the selected p is not an assumption, branch [2(ii)] applies, giving a new p-argument {} ⊢_{{q, a}} p, obtained by unfolding the chosen argument with the (single) rule in R usable for unfolding, namely with head p. This new p-argument is added to O. To compute admissibility, the algorithm also checks whether this new p-argument is already ‘dealt with’ (if the premise of a p-argument in O is already in C then that p-argument can be deemed to be ‘dealt with’, as it has already been ‘counter-attacked’, implicitly). Since none of the assumptions in the support of {} ⊢_{{q, a}} p is already a culprit in (the empty) C at this stage, this p-argument is not already ‘dealt with’ and is in O at the end of step 2.

The next iteration (step 3) is analogous to step 2.

At step 4, the selected premise a is an assumption, thus branch [2(i)] applies. Here the algorithm allows a non-deterministic choice: whether to ignore the assumption or not. Once an assumption is ignored, it is ‘marked’ and can no longer be selected. Ignoring an assumption amounts to deciding not to pick it as a culprit in the chosen opponent argument, and is important to guarantee completeness of dispute derivations (namely that one can be generated if the input is ‘acceptable’, see Dung et al., 2006). In our example derivation, a is not ignored and, since it is not already a defence (in D) or, for admissibility, a culprit (in C), branch [2(i)(c)] applies, a is added to C and a ‘counter-attack’ against {a} ⊢_{} p is started in P. The (actual) argument {a} ⊢_{} p is dropped from O and, together with an attack from it to {d} ⊢_{} d, is added to the dialectical structure (see Figure 5).

Step 5 applies branch [1(ii)] for σ=r. Here, a ‘good’ rule is a rule with head r and not containing any culprits in its body (if no such ‘good’ rule exists then the derivation is aborted). The choice of one such rule is non-deterministic, and there may be several choices possible in some cases (but not in this example). The chosen rule is r ← b, c, used to unfold {} ⊢_{r} r to give the new p-argument {} ⊢_{{b, c}} r. All assumptions in the premises of this newly generated p-argument are used to expand D. In general, for admissibility, all amongst these assumptions already in D would be put in the ‘marked’, rather than ‘unmarked’, support of the newly generated p-argument. Since D∩{b, c}={}, no ‘marking’ needs to be performed in our example. The p-argument {} ⊢_{{b, c}} r has ‘unmarked’ elements, so it is in P at the end of step 5.

The remaining steps are similar to earlier steps, except that, at step 8 and step 9, p-arguments ‘disappear’ from O since there are no rules in R for s and t (when applying branch [2(ii)], namely k=0 in the flowchart). The derivation is successful and computes defence set {d, b, c} (which is admissible and grounded, as seen in Example 5.4), culprits {a} and the dialectical tree of Figure 5.

When derivations are aborted, this does not mean that no successful derivation for the same input sentence exists, but solely that the non-deterministic choices made in that derivation did not lead to success.

Alternative derivations, success and correctness. There are several other successful dispute derivations for d in Example 5.4, computing the same defence set and culprits but potentially different dialectical structures. For example, consider steps 0-2, 4-9 in Figure 4. They give another successful derivation for d, but with dialectical structure

A different dispute derivation would have been obtained if the selection operator had picked c rather than b at step 6. This operator would still be patient. A further alternative dispute derivation for d, w.r.t. the same (patient) selection operator of Figure 4, is obtained by selecting s in O after step 6, leading to

A further alternative derivation can be obtained by selecting t, rather than s, in O after step 7 in the original derivation, leading to

The choice of opponent/proponent, the choice of argument in proponent/opponent and the selection operator are all parameters of dispute derivations (Toni, 2013), decided up-front before the derivations are started, and determining which alternative derivations are obtained. However, the choice of these parameters does not affect soundness, namely for all possible choices the computed defence set is ‘winning’ (namely dispute derivations are sound). Moreover, for a large class of ABA frameworks (namely p-acyclic ones (Dung et al., 2007; Toni, 2013)) the existence of derivations computing ‘winning’ defence sets for ‘winning’ sentences is guaranteed (namely dispute derivations are complete, for p-acyclic ABA frameworks). Note that the choice of parameters may affect speed and computation time, and parallel programming techniques can be used beneficially to explore different choices of parameters concurrently (see Craven, Toni, Hadad, Cadar, & Williams, 2012).

In general, also, alternative dispute derivations may be obtained depending on the available rules in R (as there is a non-deterministic choice point at branch [1(ii)]), and depending on whether assumptions in the opponent's arguments are ignored or not (again a non-deterministic choice, see branch [2(i)(a)]). For example, if an additional rule for r were in R, then at step 5 a different (potential) argument may have been obtained in P, possibly giving rise to a different successful derivation. Moreover, if q ← c were in R rather than q ←, then at step 3 {} ⊢_{{a, c}} p would be obtained in O and whichever of a and c, if selected, could be ignored. Some of these non-deterministic choices may give rise to a successful derivation and some may not. For example, ignoring a in {} ⊢_{{a, c}} p would not give a successful dispute derivation (as c cannot be a culprit, as it cannot be counter-attacked, since there is no argument against it).

Filtering. Dispute derivations incorporate various kinds of filtering, some common to all types of dispute derivations, some different for computing different semantics. We illustrate the common forms of filtering for the ABA framework in Example 5.4, but with R extended with rules s ← a, b, c and t ← d, p. Consider input sentence s: obviously, this is neither admissible nor grounded. Consider the following attempt to construct a dispute derivation for this sentence (again, ignoring the Args and Att components):

At this point, if it is the opponent's turn, then whichever possible culprit is selected in O (by applying [2(i)]), this is already a defence and the derivation is aborted. This form of filtering is referred to as filtering of culprits by defences.

Consider now input sentence t, again neither admissible nor grounded, and the following attempt to construct a dispute derivation for this sentence:

At this point, if it is the proponent's turn and the first potential argument {d} ⊢_{t} p in P is chosen, p is necessarily selected and [1(ii)] applies: there is only a candidate rule for p, i.e. p ← q, a, and this is not ‘good’, since a is already a culprit and cannot also be added to the defence set. Thus the derivation is aborted. This form of filtering is referred to as filtering of defences by culprits.

Both these forms of filtering guarantee that the computed defence set does not attack itself, an essential condition for admissibility (and groundedness). E.g., in the case of input sentence s, {a, b, c} attacks itself (as {b, c} ⊢ r attacks {a} ), and, in the case of input sentence t, {a, d} attacks itself (as {a} ⊢ p attacks {d} ).

We illustrate the third kind of filtering, used for admissible (and ideal) input sentences, in the context of Example 5.1. The following is a successful dispute derivation for input sentence b (this is admissible but not grounded):

At step 4, applying [1(ii)], filtering of defences by defences is applied to avoid generating the potential argument {} ⊢_{b} c_a, whose (‘unmarked’) support is already a subset of the defence set. This form of filtering is not applied for the grounded semantics (and indeed b is not grounded). It is used for the admissible (and ideal) semantics in order to successfully terminate in the presence of loops (as in this example) and/or to avoid recomputation.

The last form of filtering, filtering of culprits by culprits, is similarly applied, for the admissible (and ideal) semantics, to successfully terminate and/or to avoid recomputation.

The latter two forms of filtering (of defences by defences and of culprits by culprits) are performed by the bits in bold in the flowchart in Figure 3.

Systems. Several systems are available for computing successful dispute derivation for admissible and grounded sentences, namely CaSAPI,99 proxdd1010 and grapharg.1111 These are implementations of the dispute derivations of Gaertner and Toni (2007), Toni (2013), and Craven, Toni, and Williams (2013), respectively. The latter incorporates a form of minimality of arguments. All systems are in Prolog. They all take, as input, an ABA framework and a sentence, whose ‘acceptability’ is under investigation, and output, when possible, a dispute derivation and its outcome.

8.Knowledge representation and reasoning: FAQs

In this section we summarise answers to some most FAQs on how to use ABA for knowledge representation and reasoning purposes. We organise the FAQs and answers in three groups, respectively, concerning (1) the format of ABA frameworks, (2) the types of arguments and attacks available in ABA, and (3) the semantics or computational mechanisms for ABA frameworks.

9.Conclusion

We have provided a brief introduction to several essential features of ABA, a form of structured argumentation that has found several applications in practice (and whose development has been driven by applications) and is supported by solid theoretical foundations as well as usable computational mechanisms and systems.

For lack of space, we have ignored some important aspects, including computational complexity and the deployment of ABA in multi-agent settings: details can be found in Dimopoulos et al. (2002) and Dunne (2009) for the former and in Fan and Toni (2011, 2012) for the latter.

ABA is still a very active research area with several avenues for future work, including: the definition of failed dispute derivations and variants of dispute derivations unconditionally complete w.r.t. several semantics (i.e. complete also for non-p-acyclic ABA frameworks); further applications, e.g. in medical and legal settings; more efficient implementations, to better support applications, possibly using parallel programming techniques along the lines of Craven et al. (2012); modelling of other forms of preferences, if demanded by applications, e.g. building up and extending the work of Fan et al. (2013); the integration of ontologies within ABA (see a discussion of this aspect in Toni (2012)); the extension of ABA with probabilistic reasoning, e.g. following Dung and Thang (2010).