Decidability in argumentation semantics

1.Introduction

Computational complexity, the focus of most formal work on algorithmic matters as these affect traditional semantics within abstract argumentation frameworks, see e.g. Dvorak and Dunne [3], addresses questions of limits on efficient solution methods. In this focus there is, usually unstated, an assumption that some form of solution method, i.e. algorithm, actually is possible. A far more fundamental concern, however, is that of computability: whether a given problem is capable of algorithmic solutions at all. Recently there has been an increasing interest in treatments of semantics through analysis of generic principle. Such work has its origins in Baroni and Giacomin [1]. In this, the central interest is not so much what makes a novel semantics distinct (and arguably useful) from previously proposed forms but rather on identifying features that all reasonable semantics ought to have in common. This approach raises a very general question: suppose we have some effective mechanism by which a semantics can be described, what is it possible in this case to say about recognising such properties computationally? The aim of the current paper is first formally to define this problem and then to establish some basic computational properties.

In some respects considering, in the context of abstract argumentation frameworks, questions such as “Is it possible to solve this problem (by an algorithm)?” rather than “Is it possible to solve this problem efficiently?” may seem strange. There are, however, good reasons for doing so. We can first note the historical significance of such questions: computability (or, as it is also referred to, recursive function theory) predates the first programmable computers by several decades: the question “Can this be solved algorithmically?” has a much longer history than its counterpart “Can this be solved by an efficient algorithm?”. Even if one accepts its historical importance, the possibility of unsolvable questions arising in the specific instance of argumentation frameworks seems unlikely and examples almost surely highly contrived and artificial: defined not so much as having a “real context” but more simply to demonstrate a point. Argumentation frameworks are directed graphs and treated, in all but a small body of work, as finite structures; in practical settings this finite aspect is always present. So if we are only concerned with the computational features of single finite objects then unsolvability is not a consideration: given a finite graph, an interpretable question about that graph’s properties (e.g. from “How many edges?” through to “What is the longest simple path between two nodes?”) we can always answer the question by an algorithmic method (albeit sometimes a rather lengthy one).

In summary, if questions of effective (as opposed to efficient) methods are going to arise, these will not be at the level of individual frameworks. Argumentation, however, has moved on from the realm of issues which can be related to a purely finite framework context. From its initial proposal, we have the concept of argument semantics as subsets of finite sets satisfying particular criteria. Here, again, we are still in a finite environment: semantics are sets of subsets, some subsets will meet the criteria and others will fail to do so. The core question becomes whether a given set meets the criteria with respect to a given framework. If this, the verification problem is computable then general issues of algorithmic solution do not arise since every question can be resolved, at worst, by explicit enumeration and piecemeal review of every subset. It is, of course, conceivable that “semantics” may be formulated in which such “list and check” methods would fail since the verification problem is itself undecidable. Yet, while imaginable as a mathematical conceit, it is hard to think of any such “semantics” arising in practice. Frameworks do not yield unsolvable questions, (practical) semantics (properties of frameworks), also fail to yield such problems. It is when we move one level higher, as is demonstrated in the present paper, and look at properties of semantics that computability becomes a non-trivial issue. Properties of classes of semantics (from the “principle based” proposal of Baroni and Giacomin [1] onwards) have proven to be an important simplification in shifting interest from a justification of novel approaches through “other proposals can’t do this” to “this approach has all of the benefits of earlier ideas and it can do this”. The principle-based analysis offers a subtle but significant direction in which novel semantics are treated. It is in this move from frameworks to properties of frameworks to properties of properties of frameworks that non-computability arises. One might ask, being aware of this issue, why computability should matter: mathematicians, after all, continue their efforts despite the implications of Gödel’s work. To be aware of the possibility of non-computability may avoid efforts to automate that which provably cannot be automated: for example, we cannot develop an algorithm that given a description of a semantics will determine whether that semantics respects the conflict-freeness principle.

The shifting from frameworks and semantics to properties of semantics does, however, raise one issue: how do we represent a property e.g. conflict-freeness in computational terms. Frameworks are directed graphs and their semantics, according to the criteria used, simply subsets of their arguments. Now it is certainly possible to enumerate all frameworks and their corresponding, say conflict-free sets. In studying computational properties of principles we need to capture an infinite range of possibilities by a finite form. The mechanisms that are needed to do so are, ultimately, those that lead to questions such as “Does this semantics σ respect this principle π?” being incapable of algorithmic solution.

The consequences of viewing properties of semantics from a computational perspective go further than basic uncomputability. If we consider the classical undecidable computational problem, The Halting Problem of Turing [7], which considers if encodings of programs will come to a halt on a given input, although undecidable in the sense that no algorithm exists which is guaranteed always to give a correct response in a finite time, there is at least a “partial decision method”: one which will recognise all positive instances. This is simply to simulate the program on its given input and report accept should this simulation end. For the classification of semantics we do not even have such partial decision methods: there is no effective algorithm guaranteed to recognise all positive (or all negative) instances. In formal language while cases such as The Halting Problem are recursively enumerable (although not recursive) natural semantic properties such as conflict-freeness fail even to be recursively enumerable.

We give preliminary background in Section 2. We assume the reader has some acquaintance with the concept of Model of Computation as captured by, among others, Turing Machines, Post Machines etc. Excellent introductory background concerning these may be found in Hopcroft, Motwani and Ullman [4] with more advanced discussion in Hopcroft and Ullman [5].

In Section 3 we present one method of encoding an argument framework and collection of subsets of its argument as a finite length binary sequence. Results are given in Section 5 and Section 6 with conclusions in Section 7.

2.Preliminaries

It will be helpful to use the shorthand Eσ(H,S) with S⊆2X for the predicate which takes the value ⊤ whenever S=σ(H). It is well known (as shown in Dung’s original paper [2]) that for any af, H,

A number of general principles for argumentation semantics have been presented in Baroni and Giacomin [1]. Among these are

3.Encodings in binary and their consequences

A device which we make extensive use of can be summarised in the following terms: we have a set of objects, O; we wish, uniquely, to describe these as words over {0,1}. Since we can order the words in {0,1}∗ (e.g. use standard lexicographic ordering and the convention 0≺1) we can use such an ordering precisely to define “the first object in O”, “the second object in O” and generally the k’th object in O: go through the words in {0,1}∗ in order, the first such word that describes a valid encoding will define the “first” object. In general the k’th word discovered that defines a valid encoding will be the k’th object. We thus have total functions over N and O:

As a simple example, consider the set

4.Languages, predicates, and argument semantics

We have described a language L as a set of words over a finite alphabet (often Σ={0,1}).

We have predicates, p, whose domain we consider to be the Natural numbers, N.

An argument semantics, σ, we treat as a set of pairs (H,S) with H an af and S⊆2X so that σ(H)=S, or equivalently that Eσ(H,S) holds.

Superficially these may seem to be three quite distinct formalisms. One of the gains of the encoding mechanisms described in the previous section is in demonstrating that all are equivalent: we can treat a language, L, as a predicate pL or argument semantics σL; we can go in the opposite direction and formulate from a predicate, p, languages over single character alphabets, Lp(N) and argument semantics σp(N). Finally we may move from an argument semantics, σ, to languages Lσ or predicates pσ. The fact that encoding schemes over some collection of objects, O can be ordered is a key tool here.

The purpose of this section is to describe these translations and introduce the notational conventions used in Section 5.

5.Decidability in argumentation semantics

In looking at properties of semantics from a computational perspective we would like these to have some desirable features, One such is given by the concept of verifiability.

A semantics, σ, is verifiable if there is a program, M, that given μ(H,{S}) as input behaves as follows:

We have shown in the previous section that any argumentation semantics describes a predicate over N and such predicates define languages of words from a single character alphabet. In computational terms, we can therefore focus on the computation of languages, L⊆{1}∗. Each such language offers an (admittedly usually highly artificial) argumentation semantics; every argumentation semantics (in the sense we have defined these) describes such a language. In computational terms we would only be interested in verifiable semantics, that is to say those for which the associated single character language, Lσ(N) has a Turing Machine program, Mσ which recognises

The proof technique, “diagonalization”, of Theorem 2 is one of the classical tools used in the study of properties of infinite structures and dates back to the late 19th century.

One consequence is,

We could deal with each of the various semantic principles that have been proposed on a case-by-case basis. We can, however, proceed in a much more general style.

For example for σ=cf we could choose TcfX=X; for σ=com, TcomX={x1}.

The case of “abstention” is of interest since, of the standard argumentation semantics, only the complete semantics has this property (conventionally unique status semantics such as the grounded only “satisfy” abstention in a rather vacuous sense).

The results above are a consequence of the languages concerned i.e. “property of a semantics σ”, failing to satisfy one of the three necessary and sufficient conditions prescribed by Rice’s Theorem for r.e. properties. Namely, let LΠ be

6.A positive result

Although many of the semantic properties of interest yield non r.e. languages and hence fail even to be partially decidable, we can conclude by presenting what is in some ways, a rather surprising positive result. This arises in the technically sophisticated concept of serializability from Thimm [6].

We first need the concept of initial sets, which Xu and Cayrol [8] introduced as the non-empty S in H such that

IS↚(H) are the unattacked initial sets of H.

IS↮(H) the unchallenged initial sets of H.

IS↔(H) the challenged initial sets of H.

The reduct of H=(X,A) with respect to S⊆X is the af, HS with arguments X∖(S∪S+) and attacks A∖{⟨p,q⟩:p∈S∪S+ or q∈S∪S+}.

Finally the concept of a semantics being serializable is presented in Thimm [6].

Let σ be a semantics, i.e. a mapping from any H to sets of subsets of X.

A state is a pair (H,S) with S⊆X.

A selector is a function α:22X×22X×22X→22X satisfying α(R,S,T)⊆R∪S∪T for all R,S,T⊆2X.

A terminator is any Boolean function β mapping states to {0,1}.

A transition takes (H,S) and T∈α(IS↚(H),IS↮(H),IS↔(H)) and returns the state (HT,S∪T).

We write (H,S)⇝(α)(H′,T) if the state (H′,T) results after a finite number of applications of α. If β(H′,T)=1 the state is terminal in which case we write (H,S)→(α,β)(H′,T).

Finally let G(α,β)(H) be

The following example is taken from Thimm [6].

Choose as selector function

It is clear that

Although Theorem 5 establishes the decidability of whether a selector function exists that moves from one state to another it is a little bit unsatisfactory in one regard: it can be shown that the preferred semantics is serializable via the selector α(X,Y,Z)=X∪Y∪Z a choice which is clearly effective. A selector function discovered by the procedure of Theorem 5 only identifies a sequence of transitions relevant to one framework.

7.Conclusions

Our main aim in this paper has been to consider a different aspect of algorithmics and argumentation semantics: that of decidability rather than computational complexity. The issue of whether algorithmic processes exist is not one that arises in typical environments: these will involve finite systems and deal with questions concerning specific semantics. Such semantics are matters that concern properties of finite sets of subsets of arguments. When, however, we start to consider argumentation semantics in the principle based terms promoted by, among others, Baroni and Giacomin [1] we face a new set of problems. In principle, it is always possible to analyze new proposals on an ad hoc basis in determining which desirable properties such have. Were it possible, however, to demonstrate adherence to given principle algorithmically such ad hoc approaches become redundant: codify the semantics in a form open to computational processing, present the codified form to a suitable program for analysis. We have shown that the main obstacle to this process is not the first aspect (finite codification of a semantics) but the second. The scale of unsolvability going beyond merely non-recursive (as in classical examples such as the Halting Problem of Turing [7]): in these when an instance is positive then it will, eventually, be accepted. Instead for semantic properties we face non-recursive enumerability: neither positive nor negative instances are guaranteed eventually to be recognized. The interplay between computation and argument semantics as described in Section 4 provides an insight into how powerful the notion of argument semantics is. Whether there are significant gains from this viewpoint is the object of study in future work.