A Series of Revisions of David Poole’s Specificity

Claus-Peter Wirth Frieder Stolzenburg

FB AI, Hochschule Harz, 38855 Wernigerode, Germany

   wirth@logic.at
fstolzenburg@hs-harz.de

SEKI Report SR–2014–02

SEKI Report http://wirth.bplaced.net/seki.html ISSN 1437-4447

SEKI is published by the following institutions:

German Research Center for Artificial Intelligence (DFKI GmbH), Germany

• Robert Hooke Str. 5, D–28359 Bremen
• Trippstadter Str. 122, D–67663 Kaiserslautern
• Campus D 3 2, D–66123 Saarbrücken

Jacobs University Bremen, School of Engineering & Science, Campus Ring 1, D–28759 Bremen, Germany

Universität des Saarlandes, FR 6.2 Informatik, Campus, D–66123 Saarbrücken, Germany

SEKI Editor:

Claus-Peter Wirth

E-mail: wirth@logic.at
WWW: http://wirth.bplaced.net

Please send surface mail exclusively to:

DFKI Bremen GmbH Safe and Secure Cognitive Systems Cartesium Enrique Schmidt Str. 5 D–28359 Bremen Germany

This SEKI Report successfully passed the following external anonymous referee process:

Referee process of the Annals of Mathematics and Artificial Intelligence and (for a short version) also the 14^{th} KR 2014 — Int. Conf. on Principles of Knowledge Representation and Reasoning, Jul 20–24, as part of the Vienna Summer of Logic, Vienna, July 9–24, 2014

A Series of Revisions of David Poole’s Specificity

Claus-Peter Wirth Frieder Stolzenburg FB AI, Hochschule Harz, 38855 Wernigerode, Germany

                    wirth@logic.at
                fstolzenburg@hs-harz.de

November 13, 2014

Abstract

In the middle of the 1980s, David Poole introduced a semantical, model-theoretic notion of specificity to the artificial-intelligence community. Since then it has found further applications in non-monotonic reasoning, in particular in defeasible reasoning. Poole tried to approximate the intuitive human concept of specificity, which seems to be essential for reasoning in everyday life with its partial and inconsistent information. His notion, however, turns out to be intricate and problematic, which — as we show — can be overcome to some extent by a closer approximation of the intuitive human concept of specificity. Besides the intuitive advantages of our novel specificity orderings over Poole’s specificity relation in the classical examples of the literature, we also report some hard mathematical facts: Contrary to what was claimed before, we show that Poole’s relation is not transitive in general. The first of our specificity orderings (CP1) captures Poole’s original intuition as close as we could get after the correction of its technical flaws. The second one (CP2) is a variation of CP1 and presents a step toward similar notions that may eventually solve the intractability problem of Poole-style specificity relations. The present means toward deciding our novel specificity relations, however, show only slight improvements over the known ones for Poole’s relation, and further work is needed for testing the viability of a workaround we suggest for applications in practice.

Keywords: artificial intelligence, positive-conditional specification, non-monotonic reasoning, specificity, defeasible reasoning

2

Contents

1 Introduction 5

2 Basic Notions and Notation 6 2.1 Specifying Rules and their Theories . . . . . . . . . . . . . . . . . . . . . 6 2.2 Secondary Aspects of our Logic . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Global Parameters for the Given Specification . . . . . . . . . . . . . . . 8 2.4 Formalization of Arguments . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.5 Quasi-Orderings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3 Motivating Examples 10

4 Toward an Intuitive Notion of Specificity 12 4.1 The Common-Sense Concept of Specificity . . . . . . . . . . . . . . . . . 12 4.2 Arguments as an Intuitive Abstraction . . . . . . . . . . . . . . . . . . . 12 4.3 The Intuitive Rôle of Activation Sets in the Definition of Specificity … 13

4.3.1 Modulo Which Theory are Activation Sets to be Compared? . . . . . 13 4.3.2 A first Sketch of a Notion of Specificity . . . . . . . . . . . . . . . . . 14

4.4 Isolation of the Defeasible Parts of a Derivation . . . . . . . . . . . . . . 15 4.4.1 Isolation of Actual Defeasible Parts in And-Trees . . . . . . . . . . . 15 4.4.2 A first approximation of Activation Sets . . . . . . . . . . . . . . . . 16 4.4.3 Growth of the Defeasible Parts toward the Leaves . . . . . . . . . . . 16 4.4.4 First Effect: Simplified Second Sketch of a Notion of Specificity … 17 4.4.5 Second Effect: Preference of the “More Concise” . . . . . . . . . . . . 17 4.4.6 Preference of the “More Precise” . . . . . . . . . . . . . . . . . . . . . 19 4.4.7 Conclusion on the Preferences . . . . . . . . . . . . . . . . . . . . . . 19

5 Requirements Specification of Specificity in Positive-Conditional Specification 20

6 Formalizations of Specificity 21 6.1 Activation Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 6.2 Poole’s Specificity Relation P1; its Minor Corrections P2, P3 . . . . . . 23 6.3 Main Negative Result: Not Transitive! . . . . . . . . . . . . . . . . . . . 26 6.4 Our Novel Specificity Ordering CP1 . . . . . . . . . . . . . . . . . . . . . 27 6.5 Relation between the Specificity Relations P3 and CP1 . . . . . . . . . . 29 6.6 Checking Up the Previous Examples . . . . . . . . . . . . . . . . . . . . 30 7 Putting Specificity to Test w.r.t. Human Intuition 32

7.1 Monotonicity of the Specificity Relations w.r.t. Conjunction . . . . . . . 32 7.2 Implementation of the Preference of the “More Precise” . . . . . . . . . . 34 7.3 Conflict between the “More Concise” and the “More Precise” . . . . . . . 36 7.4 Global Effect matters more than Fine Structure . . . . . . . . . . . . . . 37

8 Efficiency Considerations and the Specificity Ordering CP2 38 8.1 A Slight Gain in Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . 38 8.2 Comparing Derivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

8.2.1 No Pruning Required . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 8.2.2 Sets of Derivations have to be Compared . . . . . . . . . . . . . . . . 38 8.2.3 Path Criteria? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

8.3 Toward a More Efficiently Realizable Notion of Poole-Style Specificity . 41 8.3.1 Immediate Activation Sets . . . . . . . . . . . . . . . . . . . . . . . . 41 8.3.2 Special Cases with Simple Activation-Set Computation . . . . . . . . 47 8.3.3 A Step Toward Operationalization of Immediate Activation Sets … 49 8.3.4 A Specificity Relation Based on Given And-Trees . . . . . . . . . . . 53

9 Conclusion 56 9.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 9.2 Application Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 9.3 Critical Assessment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

Acknowledgments 59

References 59

1 Introduction

A possible explanation of how humans manage to interact with reality — in spite of the fact that their information on the world is partial and inconsistent — mainly consists of the following two points:

1. Humans use a certain amount of rules for default reasoning and are aware that some arguments relying on these rules may be defeasible.

2. In case of the frequent conflicting or even contradictory results of their reasoning, they prefer more specific arguments to less specific ones.

An intuitive concept of specificity plays an essential rôle in this explanation, which is interesting because it seems to be highly successful in practice, even if it were just an epiphenomenon providing an ex eventu explanation of human behavior.

On the long way approaching this proven intuitive human concept of specificity, the first milestone marks the development of a semantical, model-theoretic notion of specificity having passed first tests of its usefulness and empirical validity. Indeed, at least as the first step, a semantical, model-theoretic notion will probably offer a broader and better basis for applications in systems for common sense reasoning than notions of specificity that depend on peculiarities of special calculi or even on extra-logical procedures. This holds in particular if the results of these systems are to be accepted by human users.

David Poole has sketched such a notion as a binary relation on arguments and evaluated its intuitive validity with some examples in [Poole, 1985]. Poole’s notion of specificity was given a more appropriate formalization in [Simari & Loui, 1992]. The properties of this formalization were examined in detail in [Stolzenburg &al., 2003].

In this paper, before we give a specification of the formal requirements on any reasonably conceivable relation of specificity in § 5, we present a detailed analysis of the reasons behind our intuition that Poole’s specificity is a first step on the right way (§ 4). We expect that the results of this analysis will carry us even beyond this paper to future improved concepts of specificity, especially w.r.t. efficiency, but also w.r.t. intuitive adequacy. We hope that the closer we get to human intuition, the more efficiently our concepts can be implemented, simply because they seem to run so well on the human hardware, which — by all that we know today — is pretty slow.

Moreover, in § 6, we clearly disambiguate Poole’s specificity from slightly improved versions such as the one in [Simari & Loui, 1992], and introduce a novel specificity relation (CP1), which presents a major correction of Poole’s specificity because it removes a crucial shortcoming of Poole’s original relation (P1) and its slight improvements (P2, P3), namely their lack of transitivity.

Furthermore, in § 7, we present several examples that are to convince every carefully contemplating reader of the superiority of our novel specificity relation CP1 w.r.t. human intuition.

Finally, in § 8, we discuss efficiency issues and introduce the specificity ordering CP2, a variation of CP1, which presents a first step toward similar notions that may finally solve the intractability problem of Poole-style specificity relations, for which we also present a workaround which remains to be evaluated in practice; and then we conclude with § 9.

2 Basic Notions and Notation

Definition 2.1 (Term, Atom) A term is inductively defined to be either a function symbol applied to a (possibly empty) list of terms or a symbol for a free variable. An atom consists of a predicate symbol applied to a (possibly empty) list of terms.

In what follows, we will mainly use nullary function symbols (“constants”), such as tweety, and singulary predicate symbols, such as bird, forming atoms such as bird(tweety), which states that tweety is a bird.

2.1 Specifying Rules and their Theories

For the remainder of this paper, let us narrow the general logical setting of specificity down to the concrete framework of defeasible logic with the restrictions of positive-conditional specification with an inactive negation symbol, as found e.g. in [Stolzenburg &al., 2003] and [Chesñevar &al., 2003].

In effect, these restrictions give us the standard “definite rules” of positive-conditional specification (or Horn-clause logic). Positive-conditional specification differs from logic programming in Prolog (cf. e.g. [Kowalski, 1974], [Clocksin & Mellish, 2003]) insofar as termination issues and the order of the definite clauses are irrelevant for the semantics, and insofar as there is no cut predicate (‘!’) and no negation as failure.

Such definite rules are implications of the following form: The conclusion is an atom; the condition is a (possibly empty) conjunction of (positive) atoms which may contain extra variables (i.e. free variables not occurring in the conclusion). This is can be seen as quantifier-free first-order logic with specifications restricted to implications of the mentioned form.

We ask the reader not to get confused on the mentioned effective form of our rules by the fact that — in place of the atoms — literals resulting from an inactive negation symbol are actually admitted in the rules of Definition 2.2. This special form of negation is standard in defeasible logic for convenience in the application context (such as an argumentation framework). In this paper, however, we can consider this negation just as a form of syntactical sugar (cf. Definition 2.3, Remark 2.4).

Definition 2.2 (Literal, Rule) A literal is an atom, possibly prefixed with the symbol “¬” for negation. A rule is a literal, but possibly suffixed with a reverse implication symbol “⇐” that is followed by a conjunction of literals, consisting of one literal at least.

Definition 2.3 (Theory, Derivation) Let Π be a set of rules. The theory of Π is the set �_{Π} inductively defined to contain

• all instances of literals from Π and

• all literals L for which there is a conjunction C of literals from �_{Π} such that

L ⇐ C is an instance of a rule in Π. For �⊆ �_{Π}, we also say that Π derives �, and write Π ⊢ �.

2.2 Secondary Aspects of our Logic

Remark 2.4 (Negation Symbol “¬”) The negation symbol “¬”, which occurs in Definition 2.2 and which seemingly gets us beyond the definite rules of positive-conditional specifications by admitting literals instead of just atoms, does not have any effect on the derivations and theories considered in this paper (cf. Definition 2.3).

For instance, the literal ¬flies(edna) may actually be considered as the atom resulting from application of the predicate ¬flies to the constant symbol edna.

On the other hand, if we write an atom A as A = true, and a negated atom ¬A as the equational atom A = false, for the data type Boolean given by the constructors true and false, then the rules of our specification can be seen as positive-conditional equational specifications in the framework for positive/negative-conditional equational specification found in [Wirth & Gramlich, 1994], [Wirth, 1997; 2009].^{1}

In the application context, of course, the literals ¬flies(edna) and flies(edna) will be considered to be contradictory (cf. Definition 2.5), but this is a secondary and non-essential notion built on top of our derivations and theories, which do not rely on this notion.

As a consequence, none of the results in this paper relies on this special negation symbol. To the contrary, in the weakness of our logical theories we see an indication for the generality of our results (cf. Remark 2.6).

To distinguish the inactive negation here from negation as failure and from any other form of negation playing an active rôle in derivation, the symbol “∼” is sometimes used in the literature of defeasible logic in place of our more standard symbol “¬”.

Definition 2.5 (Contradictory Sets of Rules) A set of rules Π is called contradictory if there is an atom A such that Π ⊢ {A, ¬A}; otherwise Π is non-contradictory.

Remark 2.6 (Weakness of Our Logical Theories) On the one hand, {A, ¬A ⇐ A} is contradictory according to Definitions 2.3 and 2.5.

On the other hand, {A ⇐ ¬A, ¬A ⇐ A} is non-contradictory according to these definitions, although we can infer both A and ¬A from {A ⇐ ¬A, ¬A ⇐ A} in classical (i.e. two-valued) logic.

For the case of our very limited formal language, our notions of consequence and contradiction are equivalent both to intuitionistic logic and to the three-valued logic where ¬ and ∧ are given as usual,^{2} but (following neither Kleene nor Łukasiewicz) implication has to be defined via

(A⇐TRUE) = A,  (A⇐FALSE) = TRUE,  (A⇐UNDEF) = TRUE.

1Note, however, that derivability is invariant under this equivalence transformation on atoms only if our specification is non-contradictory in the sense of Definition 2.5, in which case also the equational specification is consistent in the sense of true ≠ false.

2The standard interpretation is that TRUE is 1, UNDEF is \frac{1}{2}, FALSE is 0, ¬A is 1−A, and A∧B is min{A, B}. In other words: ¬TRUE = FALSE, ¬UNDEF = UNDEF, ¬FALSE = TRUE; TRUE∧A = A, UNDEF∧TRUE = UNDEF, UNDEF∧UNDEF = UNDEF, UNDEF∧FALSE = FALSE, FALSE∧A = FALSE.

2.3 Global Parameters for the Given Specification

Throughout this paper, we will assume a set of literals Π^{F} and two sets of rules Π^{G}, Δ (cf. Definition 2.2) to be given:

• A set Π^{F} of literals meant to describe the \underline{f}acts of the concrete situation under consideration,

• a set Π^{G} of \underline{g}eneral rules meant to hold in all possible worlds,^{3} and

• a set Δ of \underline{d}efeasible (or default) rules meant to hold in most situations.

The set Π := Π^{F} ∪ Π^{G} is the set of strict rules that — contrary to the defeasible rules — are considered to be safe and are not doubted in the concrete situation.

2.4 Formalization of Arguments

Whether a rule is a strict one from Π or a defeasible one from Δ has no effect on theories and derivations (cf. Definition 2.3). If a contradiction occurs, however, we will narrow the defeasible rules from Δ down to a subset A of its ground instances (i.e. instances without free variables) — such that no further instantiation can occur. Such a subset, together with the literal whose derivation is in focus, is called an argument. With implicit reference to the given sets of rules Π and Δ, the formal definition is as simple as follows.

Definition 2.7 ([Contradictory] [Minimal] Argument) (A, L) is an argument if A is a set of ground instances of rules from Δ and A∪Π ⊢ {L}. (A, L) is a minimal argument if A is an argument, but (A′, L) is not an argument for any proper subset A′ ⊊ A. An argument (A, L) is contradictory if A ∪ Π is a contradictory set of rules.

Remark 2.8 (Non-Ground Arguments) From a refined standpoint, what we actually need is not exactly a set A of ground instances, but just of the instances applied in the derivation. Then, however, we have to freeze the variables in A because they must not be instantiated in the derivation A∪Π ⊢ {L}. We avoid this refinement here until we come to § 8.3, because it does not play an essential rôle before and because we want to stay within the traditional framework as long as possible to facilitate a more direct comparison.

3In the approach of [Stolzenburg &al., 2003], the set Π^{G} must not contain mere literals (without suffixed condition). To obtain a more general setting, we omit this additional restriction in the context of this paper, simply because it is neither intuitive nor required for our framework here. For the actual occurrence of a literal in Π^{G}, see the discussion of Example 7.7 in § 7.4.

Remark 2.9 (Minimality and Non-Contradiction of Arguments) Some authors (cf. e.g. [Stolzenburg &al., 2003], [Chesñevar &al., 2003]) require all arguments

1. to be minimal arguments, and
2. to be non-contradictory.

Because non-minimal as well as contradictory arguments often occur in practical situations, there is no use-oriented justification for any of these requirements.

For requirement 1 there is no conceptual justification, either, because the non-minimal arguments become inessential by our preference on specific arguments, in the sense that for every argument there must be a minimal sub-argument that is at least as specific, cf. Corollaries 6.7, 6.13, and 8.11.

Because being contradictory is only a secondary aspect of our logic (cf. § 2.2), there is no conceptual justification for requirement 2, either.

To obtain a more general setting in the comparison of arguments, we omit these restrictions in the context of this paper, where they turned out to be completely superfluous. In particular, the omission of these requirements has no effect on the results of this paper.

2.5 Quasi-Orderings

We will use several binary relations comparing arguments according to their specificity. For any relation written as ≲_{N} (“being more or equivalently specific w.r.t. N”), we set

≳_{N} := { (X, Y) | Y ≲_{N} X }  (“less or equivalently specific”),
≈_{N} := ≲_{N} ∩ ≳_{N}  (“equivalently specific”),
<_{N} := ≲_{N} \ ≳_{N}  (“properly more specific”),
≤_{N} := <_{N} ∪ { (X, X) | X is an argument }  (“more specific or equal”),
△_{N} := { (X, Y) X, Y are arguments with X ≴_{N} Y and X ≵_{N} Y } (“incomparable w.r.t. specificity”).

A quasi-ordering is a reflexive transitive relation. An (irreflexive) ordering is an irreflexive transitive relation. A reflexive ordering (also called: “partial ordering”) is an anti-symmetric quasi-ordering. An equivalence is a symmetric quasi-ordering.

Corollary 2.10 If ≲_{N} is a quasi-ordering, then ≈_{N} is an equivalence, <_{N} is an ordering, and ≤_{N} is a reflexive ordering.

3 Motivating Examples

For ease of distinction, we will use the special symbol “←” as a syntactical sugar in concrete examples of defeasible rules from Δ, instead of the symbol “⇐”, which — in our concrete examples — will be used only in strict rules.

Moreover, in our graphical illustrations we will indicate membership in Π^{F} by double underlining.

Example 3.1 (Example 1 of [Poole, 1985])

Π_{3.1}^{F} := \{ \begin{matrix}bird(tweety), \\ emu(edna) \end{matrix} \} ,
Π_{3.1}^{G} := \{ \begin{matrix}bird(x) ⇐ emu(x), \\ ¬flies(x) ⇐ emu(x) \end{matrix} \} ,
Δ_{3.1} := { flies(x) ← bird(x) } ,
A_{2} := { flies(edna) ← bird(edna) }.

¬flies(edna) flies(edna)  flies(tweety)

bird(edna)

bird(tweety)

\underline{\underline{emu(edna)}} A2

We have �_{Π_{3.1}} = {bird(tweety), emu(edna), bird(edna), ¬flies(edna)}, �_{Π_{3.1}∪Δ_{3.1}} = {flies(edna), flies(tweety)} ∪ �_{Π_{3.1}}.

It is intuitively clear that we prefer the argument (∅, ¬flies(edna)) to the argument (A_{2}, flies(edna)), simply because the former does not use any defeasible rules. We will further discuss this in Example 6.17.

Let us see what happens to Example 3.1 if we are not so certain anymore that no emu can fly and turn the general rule (¬flies(x) ⇐ emu(x)) ∈ Π_{3.1}^{G} into a defeasible one in the following example.

Example 3.2 (Example 2 of [Poole, 1985])

Π_{3.2}^{F} := \{ \begin{matrix}bird(tweety), \\ emu(edna) \end{matrix} \} ,
Π_{3.2}^{G} := { bird(x) ⇐ emu(x) } ,
Δ_{3.2} := \{ \begin{matrix}¬flies(x) ← emu(x), \\ flies(x) ← bird(x) \end{matrix} \} .
A_{1} := { ¬flies(edna) ← emu(edna) }.
A_{2} := { flies(edna) ← bird(edna) }.

¬flies(edna) flies(edna)  flies(tweety)

bird(edna)

bird(tweety)

\underline{\underline{emu(edna)}} A2 A1

We have �_{Π_{3.2}} = {bird(tweety), emu(edna), bird(edna)}, �_{Π_{3.2}∪Δ_{3.2}} = {¬flies(edna), flies(edna), flies(tweety)} ∪ �_{Π_{3.2}}.

It is intuitively clear that we prefer the argument (A_{1}, ¬flies(edna)) to the argument (A_{2}, flies(edna)), simply because the defeasible derivation of the former is based on emu(edna), and because this is more specific than bird(edna), on which the derivation of the latter argument is based. We will further discuss this in Example 6.19.

Let us see what happens to Example 3.2 if we doubt that emus are birds.

Example 3.3 (Renamed Subsystem of Example 3 of [Poole, 1985])

Π_{3.3}^{F} := { emu(edna) } ,  Π_{3.3}^{G} := ∅,
Δ_{3.3} := \{ \begin{matrix}¬flies(x) ← emu(x), \\ flies(x) ← bird(x), \\ bird(x) ← emu(x) \end{matrix} \} ,
A_{1} := { ¬flies(edna) ← emu(edna) }.
A_{2} := \{ \begin{matrix}flies(edna) ← bird(edna), \\ bird(edna) ← emu(edna) \end{matrix} \}.

¬flies(edna) flies(edna)

bird(edna)

\underline{\underline{emu(edna)}} A1 A2 A2

We have

�_{Π_{3.3}} = {emu(edna)}, �_{Π_{3.3}∪Δ_{3.3}} = {bird(edna), flies(edna), ¬flies(edna)} ∪ �_{Π_{3.3}}.

Now it is not clear anymore whether we should prefer (A_{1}, ¬flies(edna)) to (A_{2}, flies(edna)). Both arguments are now based on emu(edna), but it is not clear whether the less specific bird(edna) — that has dropped out of �_{Π_{3.3}} — can still be considered as a basis for (A_{2}, flies(edna)). We will further discuss this in Example 6.20.

Let us now suppose that we have a lovely grandma and a grouchy and noisy grandpa, stay at their house and hear that somebody is coming into the house noisily, but cannot see yet who it is.

Example 3.4

Π_{3.4}^{F} := { somebody, noisy } ,
Π_{3.4}^{G} := \{ \begin{matrix}lovely ⇐ grandma, \\ ¬lovely ⇐ grandpa \end{matrix} \} ,
Δ_{3.4} := A_{1} ∪ A_{2}.
A_{1} := { grandpa ← somebody∧noisy },
A_{2} := { grandma ← somebody }.

¬lovely  lovely

grandpa  grandma

\underline{\underline{noisy}}  \underline{\underline{somebody}}

A1

A1

A2

Let us compare the specificity of the arguments (A_{1}, ¬lovely) and (A_{2}, lovely). We have

�_{Π_{3.4}} = {somebody, noisy}, �_{Π_{3.4}∪Δ_{3.4}} = {grandma, grandpa, lovely, ¬lovely} ∪ �_{Π_{3.4}}.

Now, because there is somebody who is noisy according to the current situation given by Π_{3.4}^{F}, it is probably grandpa because his characterization is more specific. Thus, it is intuitively clear that we would prefer (A_{1}, ¬lovely) as the more specific argument to (A_{2}, lovely). We will further discuss this in Example 6.21.

4 Toward an Intuitive Notion of Specificity

4.1 The Common-Sense Concept of Specificity

It is part of general knowledge that a criterion is [properly] more specific than another one if the “class of candidates that satisfy it” is a [proper] subclass of that of the other one.

Analogously — taking logical formulas as the criteria — a formula A is [properly] more specific than a formula B, if the model class of A is a [proper] subclass of the model class of B, i.e. if A ⊧ B [and B |̸= A].

If we consider a formula as a predicate on model-theoretic structures, its model class becomes the extension of this predicate. From this viewpoint, we can state A ⊧ B also as the syllogism “every A is B”, and also as the following Lambert diagram [Lambert, 1764, Dianoiologie, §§ 173–194].

\begin{matrix}⟵B⟶ \\ ⟵A⟶ \end{matrix}

4.2 Arguments as an Intuitive Abstraction

To enable a closer investigation of the critical parts of a defeasible derivation, we have to isolate the defeasible parts in the derivation. From a concrete derivation of a literal L, let us abstract the set A of the ground instances of the defeasible rules that are actually applied in the derivation, and form the pair (A, L), which we already called an argument in Definition 2.7 of § 2.4.

4.3 The Intuitive Rôle of Activation Sets in the Definition of Specificity

If we want to classify a derivation with defeasible rules according to its specificity, then we have to isolate the defeasible part of the derivation and look at its input formulas, so that we can see how specific these input formulas are. The input formulas are the set of those literals on which the defeasible part of the derivation is based, called the activation set for the defeasible part of the derivation. In our framework of defeasible positive-conditional specification, the only relevant property of an activation set can be the conjunction of its literals which we can represent by the set itself.^{4}

For instance, in Example 3.2 of § 3, the argument (A_{1}, ¬flies(edna)) is based only on the activation set {emu(edna)}, whereas the argument (A_{2}, flies(edna)) can also be based on the activation set {bird(edna)}, or on the union of these sets.

Moreover, in Example 3.4 of § 3, the argument (A_{1}, ¬lovely) is based only on the activation set {somebody, noisy}, whereas the argument (A_{2}, lovely) can also be based on the less specific activation set {somebody}.

4.3.1 Modulo Which Theory are Activation Sets to be Compared?

Because all literals of an activation set have been derived from the given specification, it does not make sense to compare activation sets w.r.t. the models of the entire specification. Indeed, only a comparison w.r.t. the models of a sub-specification can show any differences between them.

Therefore, we have to find out which parts of a specification (Π^{F}, Π^{G}, Δ) are to be excluded from the comparison of activation sets.

We want to have the entire set Π^{G} available for our comparison of activation sets, for the following reasons: The general and strict part Π^{G} of our specification represents the necessary and stable kernel of our rules, independent of the concrete situation under consideration given by Π^{F}, and independent of the uncertainty of our default rules Δ. Moreover, it is hardly meaningful to exclude any proper rule from Π^{G} (i.e. any rule from Π^{G} that is not just a literal); the technical reason for this will be given right at the beginning of § 4.4.3.

4A formal definition of an activation set is not needed here and would be harmful to intuition. Several different formal notions of activation sets will be found in Definition 6.1 of § 6.1 and also in Definition 8.7 of § 8.3.1.

We have to exclude Π^{F} from this comparison, however. This exclusion makes sense because the defeasible rules are typically default rules not written in particular for the given concrete situation that is formalized by Π^{F}. Moreover, as indicated before, the inclusion of Π^{F} would typically eliminate all differences between activation sets, such as it is the case in all examples of § 3.

Finally, as we want to compare the defeasible parts of derivations, we should exclude the set Δ of the defeasible rules when we compare activation sets.

Thus, on the one hand, all we can take into account from our specification is a subset of the general rules Π^{G}, and, on the other hand, we do not want to exclude any of these general rules.

All in all, we conclude that Π^{G} is that part of our specification modulo which activation sets are to be compared.

4.3.2 A first Sketch of a Notion of Specificity

Very roughly speaking, if we have fewer activation sets for the defeasible part of a derivation, then these activation sets describe fewer models (i.e. their disjunction has fewer models), which again means that the defeasible part of the derivation is more specific. Accordingly, a first sketch of a notion of specificity can now be given as follows:

An argument (A_{1}, L_{1}) is [properly] more specific than an argument (A_{2}, L_{2}) if, for each activation set H_{1} for (A_{1}, L_{1}), there is an activation set H_{2} ⊆ �_{H_{1}∪ Π^{G}} for (A_{2}, L_{2}) [but not vice versa].

Note that this notion of specificity is preliminary, and that the notion of an activation set for an argument has not been properly defined yet.

4.4 Isolation of the Defeasible Parts of a Derivation

If (A, L) is an argument (cf. § 4.2), then there is a derivation of L which is based only on those instances of defeasible rules which are contained in A. Such an argument ignores the concrete derivation, and therefore suits our model-theoretic intentions (cf. § 1). With such an argument as an abstraction of a derivation, however, we lose the possibility to isolate the actual defeasible parts of the derivation. Such a loss is typical for abstractions in general; in our case, however, the discussion of this loss in § 4.4.1 will turn out to be conceptually crucial and result in several different formal notions of activation sets.^{5}

4.4.1 Isolation of Actual Defeasible Parts in And-Trees

Let us compare this set A with an and-tree of the derivation. Every node in such a tree is labeled with the conclusion of an instance of a rule, such that its children are labeled exactly with the elements of the conjunction in the condition of this instance.

Definition 4.1 (And-Tree) Let (Π^{F}, Π^{G}, Δ) be a defeasible specification (cf. § 2.3), and let L be a literal. An and-tree T for L [and for the derivation of Φ ⊢ {L}] w.r.t. (Π^{F}, Π^{G}, Δ) is a finite, rooted tree, where every node is labeled with a literal, satisfying the following conditions:

1. The root node of T is labeled with L.

2. For each node N in T that is labeled with a literal L′, there is a strict or defeasible rule (L′′_{0} ⇐ L′′_{1}∧ … ∧L′′_{k}) ∈ Π ∪ Δ, such that L′ = L′′_{0}σ for some substitution σ [with (L′′_{0}σ ⇐ L′′_{1}σ∧ … ∧L′′_{k}σ) ∈ Φ]. Moreover, the node N has exactly k child nodes, which are labeled with L′′_{1}σ, …, L′′_{k}σ, respectively.

This standard and very simple formal notion of an and-tree is meant to capture a single derivation for a single argument. It must not be confused with the compact multi-graphs that come as a synopsis with our examples (such as the ones in § 3).^{6}

An isolation of the defeasible parts of an and-tree of the derivation may now proceed as follows:

• Starting from the root of the tree, we iteratively erase all applications of strict rules. This gives us a set of trees, each of which has the application of a defeasible rule at the root.

• Starting now from the leaves of these trees, we again erase all applications of strict rules. This gives us a set of trees with the following property holding for every node: If all children of a node (if there are any) are leaves, then this node results from an application of a defeasible rule.

5See Definition 6.1 of § 6.1 and also Definition 8.7 of § 8.3.1.

6These sophisticated multi-graphs illustrate several derivations for several arguments in parallel, share sub-graphs, and may have =-edges between occurrences of the same literal L to represent alternative derivations of L (cf. Example 6.9 in § 6.2 as well as Examples 7.4 and 7.5 in § 7.2). Because these synopses are redundant in all examples, we do not provide a formalization for these multi-graphs.

4.4.2 A first approximation of Activation Sets

In a first approximation, we may now take the activation set for the original derivation to be the set of all labels L of all leaves of all resulting trees, unless the literal L is an unconditional rule from A.

The motivation for this notion of an activation set is that the conjunction of its literals is a weakest precondition for all defeasible parts of the concrete original derivation. If such a logically weakest precondition satisfies the specificity notion of § 4.3.2 as an activation set for an argument (A_{1}, L_{1}) w.r.t. a second argument (A_{2}, L_{2}), then any other precondition for all defeasible parts of the given and-tree will satisfy this notion w.r.t. (A_{2}, L_{2}) a fortiori.^{7}

4.4.3 Growth of the Defeasible Parts toward the Leaves

Note that in the set of trees resulting from the procedure described in § 4.4.1, there may well have remained instances of rules from Π^{G} connecting a defeasible root application with the defeasible applications right at the leaves. Thus — to cover the whole defeasible part of the derivation in our abstraction — we have to consider the set A∪Π^{G} instead of just the set A.

More precisely, we have to include all proper rules (i.e. those with non-empty conditions) from Π^{G}, and may also include the literals in Π^{G} because they cannot do any harm.^{8}

As a consequence, in the modeling via our abstraction A, we cannot prevent the isolated defeasible sub-trees resulting from the procedure described in § 4.4.1 from using the rules from Π^{G} to grow toward the root and toward the leaves again.^{9} Only the growth toward the leaves, however, can affect our activation sets (which are still taken to be the labels of all leaves of all resulting trees) and thereby our notion of specificity. Indeed, a growth toward the root can add to the conjunction of the given leaves only its super-conjunctions, which are irrelevant because of our focus on weakest preconditions (explained in § 4.4.2).

Let us have a closer look at the effects of such a growth toward the leaves in the most simple case. In addition to a given activation set {Q(a)}, in the presence of a general rule

Q(x) ⇐ P_{0}(x)∧ ⋯ ∧P_{n−1}(x)

from Π^{G}, we will also have to consider the activation set { P_{i}(a) | i ∈ {0, …, n−1} }.

This has two effects, which we will discuss in §§ 4.4.4 and 4.4.5.

7Note that a further dissection of the isolated defeasible parts would not in general result in activation sets that can be inferred from the strict rules in Π. Where this inference is possible, however, a further dissection leads to the special notion of activation sets given in Definition 8.7 of § 8.3.1.

8The need to include all proper rules and to exclude the literals from Π^{F} provides a motivation for simply defining Π^{G} to contain exactly the proper rules of Π, such as found in [Stolzenburg &al., 2003].

9Of course, our abstraction admits even different defeasible parts of a different and-tree that derives the same literal in focus from the same set A of instances of defeasible rules, i.e. different derivations of L from A∪Π for the same argument (A, L). The admission of these multiple derivations is actually intended in our model-theoretic treatment. The only effect on our current discussion, however, is that we would have to treat several trees disjunctively, which actually makes no difference for the ideas we are currently trying to point out.

4.4.4 First Effect: Simplified Second Sketch of a Notion of Specificity

The first effect is that we immediately realize that every model of Π^{G} in the model class that is represented by the activation set { P_{i}(a) | i ∈ {0, …, n−1} } is also in the model class represented by the activation set {Q(a)}.

Indeed, this growth toward the leaves will immediately add { P_{i}(a) | i ∈ {0, …, n−1} } as a further activation set for every argument with the activation set {Q(a)}. By this effect it is just made explicit that an argument that can be based on the activation set {Q(a)} can also be based on the activation set { P_{i}(a) | i ∈ {0, …, n−1} }. Thus — provided that there are no other activation sets — an argument that can be based on the activation set {Q(a)} is less or equivalently specific compared to any argument that can be based on { P_{i}(a) | i ∈ {0, …, n−1} }.

Therefore — if we admit the effect of a growth toward the leaves on our activation sets — we may simplify^{10} the comparison of activation sets in our first sketch of a notion of specificity of § 4.3.2 as follows:

An argument (A_{1}, L_{1}) is [properly] more specific than an argument (A_{2}, L_{2}) if, for each activation set H_{1} for (A_{1}, L_{1}), this set H_{1} is also an activation set for (A_{2}, L_{2}) [but not vice versa].

4.4.5 Second Effect: Preference of the “More Concise”

The second effect, however, is that an argument (A_{2}, L_{2}) that gets along with {Q(a)} becomes even properly less specific than an argument (A_{1}, L_{1}) that actually requires { P_{i}(a) | i ∈ {0, …, n−1} } and does not get along with {Q(a)},^{11} simply because (A_{2}, L_{2}) has the additional activation set {Q(a)}.

The resulting preference of (A_{1}, L_{1}) to (A_{2}, L_{2}) as being properly more specific is usually called preference of the “more concise”, cf. e.g. [Stolzenburg &al., 2003, p. 94], [García & Simari, 2004, p.108]. Although — to the best of our knowledge — this notion has never been formally defined, roughly speaking it is — for an instantiated rule Q(a) ⇐ P_{0}(a)∧ ⋯ ∧P_{n−1}(a) of the specification — the preference of an argument that gets along with the conclusion {Q(a)} of the instantiated rule as an activation set, instead of actually requiring the condition { P_{i}(a) | i ∈ {0, …, n−1} }.

For instance, in Example 3.2 of § 3, an argument that gets along with {bird(edna)} is properly less specific than one that actually requires {emu(edna)}, in the sense that emu(edna) is more concise than bird(edna).

10Note that we have replaced here the option to choose some activation set H_{2} ⊆ �_{H_{1}∪ Π^{G}} of the first sketch with the restrictive determination H_{2} := H_{1}. This simplifying restriction applies here for the following reason: If H_{2} ⊆ �_{H_{1}∪ Π^{G}} is an activation set for (A_{2}, L_{2}), then H_{1} is an activation set for (A_{2}, L_{2})

as well, provided that we admit the first effect of a growth toward the leaves via Π^{G} on our activation sets.

11This can happen only if we have { P_{i}(a) | i ∈ {0, …, n−1} } ⊈ {Q(a)}, i.e. only if n ≠ 0.

The problem now is that the statement

Q(a) |̸= P_{0}(a)∧ ⋯ ∧P_{n−1}(a),

— which is required to justify this preference — is not explicitly given by the specification (Π^{F}, Π^{G}, Δ).

Nevertheless — if we do not just want to see it as a matter-of-fact property of notions of specificity in the style of Poole — we could justify the preference of the “more concise” by imposing the following best practice on positive-conditional specification:

If we write an implication in form of a rule

Q(x) ⇐ P_{0}(x)∧ ⋯ ∧P_{n−1}(x)

into a positive-conditional specification Π of strict (i.e. non-defeasible) knowledge, and if we do not intend that the implication is proper in the sense that its converse does not hold in general, then we ought to specify the full equivalence by adding the rules P_{i}(x) ⇐ Q(x) (i ∈ {0, …, n−1}) to the specification.^{12}

Under this best practice of specification, if we find such a rule without the specification of its full equivalence, then it is not intended to exclude models where Q holds for some object a, but not all of the P_{i} do. This means that if we find such a rule in the strict and general part Π^{G} of a specification, then it is reasonable to assume that the implication is proper w.r.t. the intuition captured in the defeasible rules in Δ.

As a consequence, it makes sense to consider a defeasible argument based on { P_{i}(a) | i ∈ {0, …, n−1} } to be properly more specific than an argument that can get along with Q(a).

⟵Q(a)⟶
⟵⋀_{i} P_{i}(a)⟶
⟵P_{k}(a)⟶

Remark 4.2 (Justification for Preference of the “More Concise”

Not Valid for Defeasible Rules)

Note that our justification for the preference of the “more concise” does not apply, however, if Q(x) ⇐ P_{0}(x)∧ ⋯ ∧P_{n−1}(x) is a defeasible rule instead of a strict one, because we then have the following three problems when trying to justify preference of the “more concise”:

• The implication given by the rule is not generally intended (otherwise the rule should be a strict one).

• Moreover, we cannot easily describe the actual instances to which the default rule is meant to apply (otherwise this more concrete description of the defeasible rule should be stated as strict rules).

• The direct treatment of a defeasible equivalence neither has to be appropriate as a default rule in the given situation, nor do we have any means to express a defeasible equivalence in the current setting.

Accordingly, there is, for instance, no clear reason to prefer the first argument of Example 3.3 in § 3 to the second one. This will be discussed in more detail in Example 6.20.

4.4.6 Preference of the “More Precise”

If we consider an argument requiring an activation set { P_{i}(a) | i ∈ {0, …, n} } to be properly more specific than an argument that gets along with a proper subset { P_{i}(a) | i ∈ I } for some index set I ⊊ {0, …, n}, then the resulting preference is usually called preference of the “more precise”, cf. e.g. [Stolzenburg &al., 2003, p. 94], [García & Simari, 2004, p.108]. An example for the preference of the “more precise” is Example 3.4 of § 3.

There is, however, an exception from this preference to be observed, namely the case that we can actually derive the set from its subset with the help of Π^{G}. In this case, the above-mentioned growth toward the leaves with rules from Π^{G} again implements the approximation of the subclass relation among model classes via the one among activation sets.^{13}

Apart from this exception, there is again a problem, namely that it is not the case that

⋀_{i∈I} P_{i}(a) |̸= ⋀_{i∈{0,...,n}} P_{i}(a)

would be explicitly given by the specification via (Π^{F}, Π^{G}, Δ).

Nevertheless — if we do not just want to see it as a matter-of-fact property of notions of specificity in the style of Poole — we could justify also the preference of the “more precise” by imposing the following best practice on positive-conditional specification:

If we want to exclude the above non-consequence, then we ought to specify, for each j ∈ {0, …, n}\I, a rule like P_{j}(x) ⇐ ⋀_{i∈I} P_{i}(x).

⟵⋀_{i∈I} P_{i}(a)⟶
⟵⋀_{i∈{1,...,n}} P_{i}(a)⟶
⟵P_{k}(a)⟶

4.4.7 Conclusion on the Preferences

Let us finally point out that an acceptance of our justifications of the preferences of the “more concise” and the “more precise” is not at all a prerequisite for following our investigations on Poole’s model-theoretic notion of specificity and our correction of this notion in the following sections.

12There is one exception to this justification, however, in the practice of logic programming: If Q(x) ⇐ P_{0}(x)∧ ⋯ ∧P_{n−1}(x) is the only rule of the specification with Q as the predicate symbol of the conclusion, then it is standard in Prolog to consider this implication as an implementation of a full equivalence defining the predicate Q.

This is different in our context of positive-conditional specification here, however, where we can add and ought to add the rules P_{i}(x) ⇐ Q(x) (i ∈ {0, …, n−1}) to our specification, simply because we are not concerned with the non-termination problem of logic programming resulting from such a specification of the full equivalence (cf. § 2.1).

An alternative which is given also in logic programming is to omit the above indicated rule and to replace each occurrence of each Q(t) with P_{0}(t)∧ ⋯ ∧P_{n−1}(t), respectively.

Moreover, in the frequent case that several cases of the definition of a predicate are spread over several rules, the implications definitely tend to be proper also in logic programming, because, roughly speaking, the defined predicate is given as the proper disjunction of the conditions of the several rules.

13This approximation was discussed in § 4.4.4 and will be demonstrated in Example 7.7 of § 7.

5 Requirements Specification of Specificity in Positive-Conditional Specification

With implicit reference to a defeasible specification (Π^{F}, Π^{G}, Δ) (cf. § 2.3), let us designate Poole’s relation of being more (or equivalently) specific by “≲_{P1}”. Here, “P1” stands for “Poole’s original version”.

The standard usage of the symbol “≲” is to denote a quasi-ordering (cf. § 2.5). Instead of the symbol “≲”, however, [Poole, 1985] uses the symbol “≤”. The standard usage of the symbol “≤” is to denote a reflexive ordering (cf. § 2.5). We cannot conclude from this, however, that Poole intended the additional property of anti-symmetry; indeed, we find a concrete example specification in [Poole, 1985] where the lack of anti-symmetry of ≲_{P1} is made explicit.^{14}

The possible lack of anti-symmetry of quasi-orderings — i.e. that different arguments may have an equivalent specificity — cannot be a problem because any quasi-ordering ≲_{N} immediately provides us with its equivalence ≈_{N}, its ordering <_{N}, and its reflexive ordering ≤_{N} (cf. Corollary 2.10 of § 2.5).

By contrast to the non-intended anti-symmetry, transitivity is obviously a conditio sine qua non for any useful notion of specificity. Indeed, if we have to make a quick choice among the three mutually exclusive actions Propose, Kiss, Smile, and if we already have an argument (A_{2}, Kiss) that is more specific than another argument (A_{3}, Smile), and if we come up with yet another argument (A_{1}, Propose) that is even more specific than (A_{2}, Kiss), then, by all means, (A_{1}, Propose) should be more specific than the argument (A_{3}, Smile) as well. It is obvious that a notion of specificity without transitivity could hardly be helpful in practice.

A further conditio sine qua non for any useful notion of specificity is that the conjunctive combination of respectively more specific arguments results in a more specific argument. Indeed, if a square is more specific than a rectangle and a circle is more specific than an ellipse, then a square inscribed into a circle should be more specific than a rectangle inscribed into an ellipse. This property is called monotonicity of conjunction, which we will discuss in § 7.1. Already in [Poole, 1985], we find an example^{15} where ≲_{P1} violates this monotonicity property of the conjunction, which is described there as “seemingly unintuitive”.^{16}

Further intricacies of computing Poole’s specificity in concrete examples are described in [Stolzenburg &al., 2003],^{17} which will make it hard to implement ≲_{P1} or its minor corrections as efficiently as required in the practice of answer computation and SLD-resolution w.r.t. positive-conditional specifications.

14Here we refer to the last three sentences of § 3.2 on Page 145 of [Poole, 1985].

15Here we refer to Example 6 of [Poole, 1985, § 3.5, p.146], which we present here as our Example 7.1 in § 7.1.

16See our Example 7.1 in § 7.1 and the references there.

17Here we refer to § 3.2ff. of [Stolzenburg &al., 2003], where it is demonstrated that, for deciding Poole’s specificity relation (actually ≲_{P2} instead of ≲_{P1}, but this does not make any difference here)

for two input arguments, we sometimes have to consider even those defeasible rules which are not part of any of these arguments. See also our Example 7.4 in § 7.2.

6 Formalizations of Specificity

6.1 Activation Sets

A derivation from the leaves to the root can now be split into three phases of derivation of literals from literals. This splitting follows the discussion in § 4.4.1 on how to isolate the defeasible parts of a derivation (phase 2) from strict parts that may occur toward the root (phase 3) and toward the leaves (phase 1):

(phase 1) First we derive the literals that provide the basis for specificity considerations.

In our approach we derive the set �_{Π} here. Poole takes the set �_{Π∪Δ} instead.

(phase 2) On the basis of

• a subset H of the literals derived in phase 1,

• the first item A of a given argument (A, L), and

• the general rules Π^{G},

we derive a further set of literals �: H ∪ A ∪ Π^{G} ⊢ �.

(phase 3) Finally, on the basis of �, the literal of the given argument (A, L) is derived:

�∪ Π ⊢ {L}.

In Poole’s approach, phase 3 is empty and we simply have �= {L}. In our approach, however, it is admitted to use the facts from Π^{F} in phase 3, in addition to the general rules from Π^{G}, which were already admitted in phase 2.

With implicit reference to our sets Π = Π^{F} ∪ Π^{G} and Δ, the phases 2 and 3 can be more easily expressed with the help of the following notions.

Definition 6.1 ([Minimal] [Simplified] Activation Set) Let A be a set of ground instances of rules from Δ, and let L be a literal. H is a simplified activation set for (A, L) if L ∈ �_{H ∪ A ∪ Π^{G}} . H is an activation set for (A, L) if L ∈ �_{�∪Π} for some �⊆ �_{H ∪ A ∪ Π^{G}} . H is a minimal [simplified] activation set for (A, L) if H is an [simplified] activation set for (A, L), but no proper subset of H is an [simplified] activation set for (A, L).

Corollary 6.2 Let A be a set of ground instances of rules from Δ, and let L be a literal. Every simplified activation set for (A, L) is an activation set for (A, L).

Roughly speaking, an argument is now more (or equivalently) specific than another one if each of its activation sets is also an activation set for the other argument. Note that this follows the simplified second sketch of a notion of specificity displayed in § 4.4.4, not the first one displayed in § 4.3.2.

Activation sets that are not simplified differ from simplified ones by the admission of facts from Π^{F} (in addition to the general rules Π^{G}) after the defeasible part of the derivation is completed.^{18}

Our introduction of activation sets that are not simplified is a conceptually important correction of Poole’s approach: It must be admitted to use the facts besides the general rules in a purely strict derivation that is based on literals resulting from completed defeasible arguments, simply because the defeasible parts of a derivation (as isolated in § 4.4.1) should not get more specific by the later use of additional facts that do not provide input to the defeasible parts.^{19} Note that the difference between simplified and non-simplified activation sets typically occurs in real applications, but — except Example 7.5 in § 7.2 — not in our toy examples of § 7, which mainly exemplify the differences in phase 1.

F ∪ Π^{G} … A A ∪ Π^{G} H A A ∪ Π^{G} H

H ⊆ …  F = …
Poole’s Approach (P1, P2, P3)  �_{Π^{F}∪Π^{G}∪Δ}  H ^{20}
Our Approach (CP1, CP2)  �_{Π^{F}∪Π^{G}}  Π^{F} ^{21}

Figure 1: And-Tree with Phases 1, 2, 3.^{22}

18This can be seen in Example 7.5 of § 7, and in Example 8.1 of § 8.2.2. See also the variable F in Figure 1. 19We do not further discuss this obviously appropriate correction here and leave the construction of

examples that make the conceptual necessity of this correction intuitively clear as an exercise. Hint: Have a look at the proof of Theorem 6.16 in § 6.5. Then present two different sets of strict rules with equal derivability, where only one needs the facts in phase 3 and where the additional specificity gained by these facts violates the intuition.

20Look at Note 35 of Example 7.4 in § 7.2 to see that it may really matter for the definition of P1, P2, P3 that we do not have H ⊆ �_{Π^{F}∪Π^{G}} in general in Poole’s approach.

21Although we do not have H ⊆ Π^{F} in general in our approach, the replacement of Π^{F} with H in this table would result in fewer derivable roots for our approach, simply because we always have �_{H∪Π^{G}} ⊆ �_{Π^{F}∪Π^{G}} in our approach.

22From the leaves to the root: phase 1 (H), phase 2 (sub-trees of the defeasible parts of a derivation, with explicit defeasible root steps), phase 3 (root sub-tree). For Poole’s approach, however, the root sub-tree is still part of phase 2, whereas phase 3 is empty.

6.2 Poole’s Specificity Relation P1; its Minor Corrections P2, P3

In this section we will define the binary relations ≲_{P1}, ≲_{P2}, ≲_{P3} of “being more or equivalently specific according to David Poole” with implicit reference to our sets of facts and of general and defeasible rules (i.e. to Π^{F}, Π^{G}, and Δ, respectively).

The relation ≲_{P1} of the following definition is precisely Poole’s original relation ≥ as defined at the bottom of the left column on Page 145 of [Poole, 1985]. See § 5 for our reasons to write “≳” instead of “≥” as a first change. Moreover, as a second change required by mathematical standards, we have replaced the symbol “≳” with the symbol “≲” (such that the smaller argument becomes the more specific one), so that the relevant wellfoundedness becomes the one of its ordering < instead of the reverse >.

Definition 6.3 (≲_{P1} : David Poole’s Original Specificity) (A_{1}, L_{1}) ≲_{P1} (A_{2}, L_{2}) if (A_{1}, L_{1}) and (A_{2}, L_{2}) are arguments, and if, for every H ⊆ �_{Π∪Δ} that is a simplified activation set for (A_{1}, L_{1}) but not a simplified activation set for (A_{2}, L_{1}), H is also a simplified activation set for (A_{2}, L_{2}).

The relation ≲_{P2} of the following definition is the relation ⪰ of Definition 10 on Page 94 of [Stolzenburg &al., 2003] (attributed to [Poole, 1985]). Moreover, the relation >_{spec} of Definition 2.12 on Page 132 of [Simari & Loui, 1992] (attributed to [Poole, 1985] as well) is the relation <_{P2} := ≲_{P2} \ ≳_{P2}.

Definition 6.4 (≲_{P2} : Standard Version of David Poole’s Specificity) (A_{1}, L_{1}) ≲_{P2} (A_{2}, L_{2}) if (A_{1}, L_{1}) and (A_{2}, L_{2}) are arguments, and if, for every H ⊆ �_{Π∪Δ} that is a simplified activation set for (A_{1}, L_{1}) but not a simplified activation set for (∅, L_{1}), H is also a simplified activation set for (A_{2}, L_{2}).

The only change in Definition 6.4 as compared to Definition 6.3 is that “(A_{2}, L_{1})” is replaced with “(∅, L_{1})”. We did not encounter any example yet where this intuitively most appropriate correction of the variant “(A_{2}, L_{1})” of Definition 6.3 makes any difference to “(∅, L_{1})” in Definition 6.4, which is standard in the publications of the last two decades.

The relations ≲_{P1} and ≲_{P2} were not meant to compare arguments for literals that do not need any defeasible rules — or at least they do not show an intuitive behavior on such arguments, as shown in Example 6.5.

Example 6.5 (Minor Flaw of ≲_{P1} and ≲_{P2})

Π_{6.5}^{F} := { thirst } ,
Π_{6.5}^{G} := { drink ⇐ thirst } ,
Δ_{6.5} := A_{2}.
A_{2} := { beer ← thirst }.

drink  beer

\underline{\underline{thirst}} A2

Let us compare the specificity of the arguments (A_{2}, beer) and (∅, drink), meaning that we should have a beer or else an arbitrary drink at our own choice, respectively.

We have �_{Π_{6.5}} = {thirst, drink}, �_{Π_{6.5}∪Δ_{6.5}} = {beer} ∪ �_{Π_{6.5}}.

We have (A_{2}, beer) ≲_{P2} (∅, drink) because for every H ⊆ �_{Π_{6.5}∪Δ_{6.5}} that is a simplified activation set for (A_{2}, beer), but not a simplified activation set for (∅, beer), we have H = {thirst}, which is a simplified activation set also for (∅, drink).

We have (∅, drink) ≲_{P2} (A_{2}, beer) because there cannot be a simplified activation set for (∅, drink) that is not a simplified activation set for (∅, drink).

All in all, we get^{23} (A_{2}, beer) ≈_{P2} (∅, drink), although (∅, drink) should be strictly preferred to (A_{2}, beer) according to intuition, simply because an argument that does not require any defeasible rules should always be strictly preferred to a comparable argument that does actually require defeasible rules.

To overcome this minor flaw, which consists in the inconvenience of not in general preferring a non-defeasible argument to a comparable defeasible one, we finally add an implication as an additional requirement in Definition 6.6. This implication guarantees that no argument that requires defeasible rules can be more or equivalently specific than an argument that does not require any defeasible rules at all.

Definition 6.6 (≲_{P3} : Rather Unflawed Version of David Poole’s Specificity) (A_{1}, L_{1}) ≲_{P3} (A_{2}, L_{2}) if (A_{1}, L_{1}) and (A_{2}, L_{2}) are arguments, L_{2} ∈ �_{Π} implies L_{1} ∈ �_{Π}, and if, for every H ⊆ �_{Π∪Δ} that is a [minimal]^{24} simplified activation set for (A_{1}, L_{1}) but not a simplified activation set for (∅, L_{1}), H is also a simplified activation set for (A_{2}, L_{2}).

Corollary 6.7 If (A_{1}, L_{1}), (A_{2}, L_{2}) are arguments with A_{1} ⊆ A_{2}, then any of the following conditions is sufficient for (A_{1}, L_{1}) ≲_{P3} (A_{2}, L_{2}):

1. L_{1} = L_{2}.

2. L_{2} ∈ �_{Π} ⇒ L_{1} ∈ �_{Π} and {L_{1}} ∪ A_{2} ∪ Π^{G} ⊢ {L_{2}},

3. A_{1} = ∅ (which implies L_{1} ∈ �_{Π} by Definition 2.7).^{25}

As every simplified activation set that passes the condition of Definition 6.3 also passes the one of Definitions 6.4 and 6.6, we get the following corollary of these three definitions.

Corollary 6.8 ≲_{P3} ⊆ ≲_{P2} ⊆ ≲_{P1}.

By Corollaries 6.7 and 6.8, ≲_{P1}, ≲_{P2}, ≲_{P3} are reflexive relations on arguments, but — as we will show in Example 6.9 and state in Theorem 6.11 — not quasi-orderings in general.

23Note that by Corollary 6.8, we will get (A_{2}, beer) ≈_{P1} (∅, drink) as well. Moreover, note that this problem does not occur in the similar Example 3.1 of § 3.

24Note that the omission of the optional restriction to minimal simplified activation sets for (A_{1}, L_{1})

in Definition 6.6 has no effect on the extension of the defined notion, simply because the additional nonminimal simplified activation sets (A_{1}, L_{1}) will then be simplified activation sets for (A_{2}, L_{2}) a fortiori.

25Exercise: Find a counterexample, however, for the conjecture that L_{1} ∈ �_{Π} implies (A, L_{1}) ≲_{P3} (A, L_{2}).

Example 6.9 (Counterexample to the Transitivities: “Choose one action!”) Suppose you meet the sexy girl Jo in a lift for a very short time, you smile at her, and she smiles back with a head akimbo. Since smiling, kissing, and proposing are mutually exclusive actions of your mouth, you have to make up your mind quickly what to do next, depending on your current level of boldness.^{26}

Π_{6.9}^{F} := { Bold, HAkimbo(Jo), Smiles(Jo), Sexy(Jo) } ,
Π_{6.9}^{G} := { Kiss ⇐ Promising(G) } ,

Δ_{6.9} := \{ \begin{matrix}Smile ← Sexy(G), \\ Kiss ← Bold∧Smiles(G)∧Sexy(G), \\ Promising(G) ← HAkimbo(G)∧Smiles(G)∧Sexy(G), \\ Propose & ← & Promising(G) & ∧ & Bold \end{matrix} \} .

A_{1} := \{ \begin{matrix}Promising(Jo) & ← & HAkimbo(Jo) & ∧ & Smiles(Jo) & ∧ & Sexy(Jo) \\ Propose & ← & Promising(Jo) & ∧ & Bold \end{matrix} \},
A_{2} := { Kiss ← Bold∧Smiles(Jo)∧Sexy(Jo) },
A_{3} := { Smile ← Sexy(Jo) }.

Compare the specificity of the arguments (A_{1}, Propose), (A_{2}, Kiss), (A_{3}, Smile) !

Propose  Kiss Kiss  Smile

Promising(Jo) \underline{\underline{Bold}}

\underline{\underline{HAkimbo(Jo)}}  \underline{\underline{Smiles(Jo)}}  \underline{\underline{Sexy(Jo)}}

A1

A1

A1

A1

A1

A2

A2

A2

A3

Lemma 6.10 There are

• a specification (Π_{6.9}^{F}, Π_{6.9}^{G}, Δ_{6.9}) without any negative literals (i.e., a fortiori, Π_{6.9}^{F} ∪ Π_{6.9}^{G} ∪ Δ_{6.9} is non-contradictory), and

• minimal arguments (A_{1}, L_{1}), (A_{2}, L_{2}), (A_{3}, L_{3}),

such that (A_{1}, L_{1}) ≲_{P3} (A_{2}, L_{2}) ≲_{P3} (A_{3}, L_{3}) ≵_{P1} (A_{1}, L_{1})
and (A_{1}, L_{1}) ≵_{P1} (A_{2}, L_{2}) ≵_{P1} (A_{3}, L_{3}).

26The nullary predicate Bold could actually be removed from all rules and facts of this example, which would still remain a counterexample to the transitivities; to the contrary, it would even improve its status by becoming a minimal counterexample. A renaming of the resulting minimal counterexample was presented as Example 5.8 in [Wirth & Stolzenburg, 2013; 2014]. The reasons we prefer the non-minimal counterexample are the following. The minimal counterexample looks artificial because the single general strict rule lacks any effect on activation sets for arguments for (A_{1}∪A_{2}, Kiss). Moreover, the minimal counterexample used to confuse the audience during presentations because the names of its predicates mixed up different cognitive categories.

Proof of Lemma 6.10

Looking at Example 6.9, we see that only the quasi-ordering properties in the last two lines of Lemma 6.10 are non-trivial. We have

�_{Π_{6.9}}  = {Bold, HAkimbo(Jo), Smiles(Jo), Sexy(Jo)},
�_{Π_{6.9}∪Δ_{6.9}} = {Promising(Jo), Propose, Kiss, Smile} ∪ �_{Π_{6.9}}.

Thus, regarding the arguments (A_{1}, Propose), (A_{2}, Kiss), (A_{3}, Smile), the implication added in Definition 6.6 as compared to Definitions 6.3 and 6.4 is always satisfied, simply because its condition is always false.

\underline{(A_{3}, Smile) ≵_{P1} (A_{1}, Propose) ≲_{P3} (A_{2}, Kiss) :} The minimal simplified activation sets for

(A_{1}, Propose) that are subsets of �_{Π_{6.9}∪Δ_{6.9}}

and no simplified activation sets for (∅, Propose) (or, without any difference, no simplified activation sets for (A_{3}, Propose)) are {Bold, HAkimbo(Jo), Smiles(Jo), Sexy(Jo)} and {Bold, Promising(Jo)}, which are simplified activation sets for (A_{2}, Kiss) — but {Bold, Promising(Jo)} is no simplified activation set for (A_{3}, Smile).

\underline{(A_{1}, Propose) ≵_{P1} (A_{2}, Kiss) ≲_{P3} (A_{3}, Smile) :} The only simplified activation set for

(A_{2}, Kiss) that is a subset of �_{Π_{6.9}∪Δ_{6.9}} and

no simplified activation set for (∅, Kiss) (such as {Promising(Jo)}) (or, without any difference, no simplified activation sets for (A_{1}, Kiss)) is {Bold, Smiles(Jo), Sexy(Jo)}, which is a simplified activation set for (A_{3}, Smile), but not for (A_{1}, Propose).

\underline{(A_{2}, Kiss) ≵_{P1} (A_{3}, Smile) :} The only minimal simplified activation set for (A_{3}, Smile) that

is a subset of �_{Π_{6.9}∪Δ_{6.9}} and no simplified activation set for

(A_{2}, Smile) is {Sexy(Jo)}, which is not a simplified activation set for (A_{2}, Kiss).

Q.e.d. (Lemma 6.10)

6.3 Main Negative Result: Not Transitive!

The relations stated in Lemma 6.10 hold not only for the given indices, but — by Corollary 6.8 — actually for all of P1, P2, P3; and so we immediately get:

Theorem 6.11 There is a specification (Π_{6.9}^{F}, Π_{6.9}^{G}, Δ_{6.9}), such that Π_{6.9}^{F} ∪ Π_{6.9}^{G} ∪ Δ_{6.9} is non-contradictory, but none of ≲_{P1}, ≲_{P2}, ≲_{P3}, <_{P1}, <_{P2}, <_{P3} is transitive. Moreover, the counterexamples to the transitivity of all these relations can be restricted to minimal arguments.

As a consequence of Theorem 6.11, the respective relations in [Poole, 1985], [Stolzenburg &al., 2003], and [Simari & Loui, 1992] are not transitive. This means that these relations are not quasi-orderings, let alone reflexive orderings.

This consequence is immediate for the relation ≥ at the bottom of the left column on Page 145 of [Poole, 1985]. Moreover, note that the consequence does not depend on the contentious question on whether our interpretation of the negation symbol ¬ essentially differs from its interpretation in [Poole, 1985]. Indeed, our counterexample to transitivity occurs in the negation-free definite-rule fragment of Poole’s original language.

Moreover, this consequence is also immediate for the relation ⪰ [Stolzenburg &al., 2003, Definition 10, p. 94] and for the relation >_{spec} [Simari & Loui, 1992, Definition 2.12, p.132], simply because we can replace ⪰ and >_{spec} with ≲_{P2} and <_{P2} in the context of Example 6.9, respectively.

Although transitivity of these relations is strongly suggested by the special choice of their symbols and seems to be taken for granted in general, we found an actual statement of such a transitivity only for the relation ⊒ of Definition 2.22 on Page 134 of [Simari & Loui, 1992], namely in “Lemma 2.23” [Simari & Loui, 1992, p.134].^{27}

Finally, note that those readers who do not see a proper conflict in our counterexample just should add to Example 6.9 some general rules such as Execute ⇐ Kiss, ¬Execute ⇐ Smile, ¬Execute ⇐ Propose, say to model the situation in one of the areas of today’s planet Earth where an unmarried woman who raises the wish to kiss has to be executed.

6.4 Our Novel Specificity Ordering CP1

In the previous section, we have seen that minor corrections of Poole’s original relation P1 (such as P2, P3) do not cure the (up to our finding of Example 6.9) hidden or even denied deficiency of these relations, namely their lack of transitivity. Our true motivation for a major correction of P3 was not this formal deficiency, but actually an informal one, namely that it failed to get sufficiently close to human intuition, which will become clear in § 7.

For these reasons, we now define our major \underline{c}orrection of \underline{P}oole’s specificity — the binary relation ≲_{CP1} — with implicit reference to our sets of facts and of general and defeasible rules (i.e. to Π^{F}, Π^{G}, and Δ, respectively) as follows.

Definition 6.12 (≲_{CP1} : 1^{st} Version of our Specificity Relation) (A_{1}, L_{1}) ≲_{CP1} (A_{2}, L_{2}) if (A_{1}, L_{1}) and (A_{2}, L_{2}) are arguments, and we have

1. L_{1} ∈ �_{Π} or

2. L_{2} ∉ �_{Π} and every H ⊆ �_{Π} that is an [minimal]^{28} activation set for (A_{1}, L_{1}) is also an activation set for (A_{2}, L_{2}).

27According to the rules of good scientific and historiographic practice, we pinpoint the violation of this “lemma” now as follows. Non-transitivity of ⊒ follows here immediately from the non-transitivity of the relation ≥_{spec} of Definition 2.15, which, however, is not identical to the above-mentioned relation ⪰, but actually a subset of ⪰, because it is defined via a peculiar additional equivalence ≈_{spec} introduced in Definition 2.14 [Simari & Loui, 1992, p.132], namely via ≥_{spec} := >_{spec} ∪ ≈_{spec} [Simari & Loui, 1992, Definition 2.15, p.132f.]. Directly from Definition 2.14 of [Simari & Loui, 1992], we get ≈_{spec} ⊆ ≈_{P2}.

Thus, by Corollary 6.8, we get ≥_{spec} ⊆ ≲_{P2} ⊆ ≲_{P1}; and so (recollecting <_{P2} ⊆ >_{spec} ⊆ ≥_{spec}) the result

(A_{1}, L_{1}) <_{P2} (A_{2}, L_{2}) <_{P2} (A_{3}, L_{3}) ≵_{P1} (A_{1}, L_{1})

of Lemma 6.10 gives us the following counterexample to transitivity:

(A_{1}, L_{1}) ≥_{spec} (A_{2}, L_{2}) ≥_{spec} (A_{3}, L_{3}) ≰_{spec} (A_{1}, L_{1}).

28Note that the omission of the optional restriction to minimal activation sets for (A_{1}, L_{1}) in Definition 6.12 has no effect on the extension of the defined notion, simply because the additional non-minimal activation sets for (A_{1}, L_{1}) will then be activation sets for (A_{2}, L_{2}) a fortiori.

Corollary 6.13 If (A_{1}, L_{1}), (A_{2}, L_{2}) are arguments with A_{1} ⊆ A_{2}, then any of the following conditions is sufficient for (A_{1}, L_{1}) ≲_{CP1} (A_{2}, L_{2}) :

1. L_{1} = L_{2}.

2. L_{2} ∈ �_{Π} ⇒ L_{1} ∈ �_{Π} and {L_{1}} ∪ Π ⊢ {L_{2}}. ^{29}

3. L_{1} ∈ �_{Π} (which is implied by A_{1} = ∅ by Definition 2.7).

The crucial change in Definition 6.12 as compared to Definition 6.6 is not the technically required emphasis it puts on the case “L_{1} ∈ �_{Π}”, which will be discussed in Remark 6.18 of § 6.6. The crucial changes actually are

(A) the replacement of “H ⊆ �_{Π∪Δ}” with “H ⊆ �_{Π}” (as explained already in phase 1 of § 6.1), and the thereby enabled

(B) omission of the previously technically required,^{30} but unintuitive negative condition on derivability (of the form “but not a simplified activation set for (∅, L_{1})”).

An additional minor change, which we have already discussed in § 6.1, is the one from simplified activation sets to (non-simplified) activation sets.

Theorem 6.14 ≲_{CP1} is a quasi-ordering on arguments.

Proof of Theorem 6.14 ≲_{CP1} is a reflexive relation on arguments because of Corollary 6.13. To show transitivity, let us assume (A_{1}, L_{1}) ≲_{CP1} (A_{2}, L_{2}) and (A_{2}, L_{2}) ≲_{CP1} (A_{3}, L_{3}). According to Definition 6.12, because of (A_{1}, L_{1}) ≲_{CP1} (A_{2}, L_{2}), we have L_{1} ∈ �_{Π} — and then immediately the desired (A_{1}, L_{1}) ≲_{CP1} (A_{3}, L_{3}) — or we have L_{2} ∉ �_{Π} and every H ⊆ �_{Π} that is an activation set for (A_{1}, L_{1}) is also an activation set for (A_{2}, L_{2}). The latter case excludes the first option in Definition 6.12 as a justification for (A_{2}, L_{2}) ≲_{CP1} (A_{3}, L_{3}), and thus we have L_{3} ∉ �_{Π} and every H ⊆ �_{Π} that is an activation set for (A_{2}, L_{2}) is also an activation set for (A_{3}, L_{3}). All in all, we get that every H ⊆ �_{Π} that is an activation set for (A_{1}, L_{1}) is also an activation set for (A_{3}, L_{3}). Thus, we get the desired (A_{1}, L_{1}) ≲_{CP1} (A_{3}, L_{3}) also in this case. Q.e.d. (Theorem 6.14)

Obviously, an argument is ranked by ≲_{CP1} firstly on whether its literal is in �_{Π}, and, if not, secondly on the set of its activation sets, which is an element of the power set of the power set of �_{Π}. So we get:

Corollary 6.15 If �_{Π} is finite, then <_{CP1} is well-founded.

29Note that, in general — contrary to Corollary 6.7(2) — A_{2} must not participate in the derivation of L_{2} from L_{1}, say in the form that there is a set of literals � with {L_{1}} ∪ A_{2} ∪ Π^{G} ⊢ � and �∪ Π ⊢ {L_{2}}, because rules from Π^{F} may have participated in the derivation of L_{1} from an activation set. The source of this difference between P3 and CP1 is the replacement of simplified activation sets in Definition 6.6 with (non-simplified) activation sets in Definition 6.12.

30See the discussion in Example 6.21 in § 6.6 on why this condition is technically required for P1, P2, and P3.

6.5 Relation between the Specificity Relations P3 and CP1

Theorem 6.16 Let Π^{<2} be the set of rules from Π that are unconditional or have exactly one literal in the conjunction of their condition.

Let Π^{≥2} be the set of rules from Π with more than one literal in their condition.

≲_{P3} ⊆ ≲_{CP1} holds if one (or more) of the following conditions hold:

1. For every H ⊆ �_{Π} and for every set A of ground instances of rules from Δ, and for �:= �_{H∪A∪Π^{G}}, we have �_{�∪Π} ⊆ �∪ �_{Π}.

2. For each instance L ⇐ L′_{0}∧ … ∧L′_{n+1} of each rule in Π^{≥2} with L ∉ �_{Π^{<2}}, we have L′_{j} ∉ �_{Π^{<2}} for all j ∈ {0, …, n+1}.

3. For each instance L ⇐ L′_{0}∧ … ∧L′_{n+1} of each rule in Π^{≥2}, we have L′_{j} ∉ �_{Π} for all j ∈ {0, …, n+1}.

4. We have Π^{≥2} = ∅.

Note that if we had improved ≲_{P3} only w.r.t. phase 1 of § 6.1, but not w.r.t. phase 3 in addition, then Theorem 6.16 would not require any condition at all. (See the proof!) This means that a condition becomes necessary by our correction of simplified activation sets to non-simplified ones, but not because of the major changes (A) and (B) of § 6.4.

Proof of Theorem 6.16

First let us show that condition 2 implies condition 1. To this end, let H ⊆ �_{Π}, let A be a set of ground instances of rules from Δ, and set � := �_{H∪A∪Π^{G}}. For an argumentum ad absurdum, let us assume �_{�∪Π} ⊈ �∪ �_{Π}. Because of Π^{F}⊆ �_{Π^{<2}}, we have �∪ Π = �∪ Π^{F} ∪ Π^{G} ⊆ �∪ �_{Π^{<2}} ∪ Π^{G}, and thus �_{�∪Π} ⊆ �_{�∪ �_{Π^{<2}} ∪ Π^{G}}, and thus �_{�∪ �_{Π^{<2}} ∪ Π^{G}} ⊈ �∪ �_{Π^{<2}} (because otherwise �_{�∪Π} ⊆ �_{�∪ �_{Π^{<2}} ∪ Π^{G}} ⊆ �∪ �_{Π^{<2}} ⊆ �∪ �_{Π}). Now � is closed under Π^{G} by definition. Moreover, �_{Π^{<2}} is closed under Π^{<2} by definition and under Π^{≥2} by condition 2. Because both of the sets of literals � and �_{Π^{<2}} are closed under Π^{G} — but nevertheless their union is not closed under Π^{G} according to �_{�∪ �_{Π^{<2}} ∪ Π^{G}} ⊈ �∪ �_{Π^{<2}} — there must be an inference step essentially based on both sets in parallel. More precisely, this means that there must be an instance L ⇐ L′_{1}∧ … ∧L′_{n} of a rule from Π^{G} with L ∉ �∪ �_{Π^{<2}}, and some i, j ∈ {1, …, n} with L′_{i} ∈ �\�_{Π^{<2}} and L′_{j} ∈ �_{Π^{<2}}\�. Then L ⇐ L′_{1}∧ … ∧L′_{n} must actually be an instance of a rule from Π^{≥2}, and L ∉ �_{Π^{<2}}, but L′_{j} ∈ �_{Π^{<2}} in contradiction to condition 2.

As condition 2 implies condition 1, condition 3 trivially implies condition 2, and condition 4 trivially implies condition 3, it now suffices to show the claim that (A_{1}, L_{1}) ≲_{CP1} (A_{2}, L_{2}) holds under condition 1 and the assumption of (A_{1}, L_{1}) ≲_{P3} (A_{2}, L_{2}). By this assumption, (A_{1}, L_{1}) and (A_{2}, L_{2}) are arguments and L_{2} ∈ �_{Π} implies L_{1} ∈ �_{Π}. If L_{1} ∈ �_{Π} holds, then our claim holds as well. Otherwise, we have L_{1}, L_{2} ∉ �_{Π}, and it suffices to show the sub-claim that H is an activation set for (A_{2}, L_{2}) under the additional sub-assumption that H ⊆ �_{Π} is an activation set for (A_{1}, L_{1}). Under the sub-assumption we also have H ⊆ �_{Π∪Δ} because of �_{Π} ⊆ �_{Π∪Δ}, and, for � := �_{H∪A_{1}∪Π^{G}}, we have L_{1} ∈ �_{�∪ Π}, and then, by condition 1, L_{1} ∈ �∪ �_{Π}. Then, by our current case of L_{1}, L_{2} ∉ �_{Π}, we have L_{1} ∈ �. Thus, H is a simplified activation set for (A_{1}, L_{1}).

Let us now provide an argumentum ad absurdum for the assumption that H is a simplified activation set also for (∅, L_{1}): Then we would have L_{1} ∈ �_{H∪Π^{G}}, and because of H ⊆ �_{Π} and Π^{G} ⊆ Π we get L_{1} ∈ �_{�_{Π}∪Π} = �_{Π} — a contradiction to our current case of L_{1}, L_{2} ∉ �_{Π}.

All in all, by our initial assumption, H must now be a simplified activation set for (A_{2}, L_{2}) and, a fortiori by Corollary 6.2, an activation set for (A_{2}, L_{2}), as was to be shown for our only remaining sub-claim. Q.e.d. (Theorem 6.16)

6.6 Checking Up the Previous Examples

With the help of Theorem 6.16, we can now analyze the examples of § 3, and also check how our relation CP1 behaves in case of our counterexample to transitivity. Note that condition 4 of Theorem 6.16 is satisfied for all of these examples.

Example 6.17 (continuing Example 3.1 of § 3) We have (A_{2}, flies(edna)) ≴_{CP1} (∅, ¬flies(edna))

because flies(edna) ∉ �_{Π_{3.1}} and ¬flies(edna) ∈ �_{Π_{3.1}}.

We have (∅, ¬flies(edna)) ≲_{P3} (A_{2}, flies(edna)) by Corollary 6.7(3).

All in all, by Theorem 6.16, we get (∅, ¬flies(edna))<_{CP1}(A_{2}, flies(edna)) and (∅, ¬flies(edna)) <_{P3} (A_{2}, flies(edna)).

Remark 6.18 One may ask why we did not define an additional quasi-ordering, say ≲_{CP0}, simply by replacing the two conditions of Definition 6.12 with the single condition

“L_{2} ∈ �_{Π} implies L_{1} ∈ �_{Π}, and every H ⊆ �_{Π} that is an [minimal] activation
set for (A_{1}, L_{1}) is also an activation set for (A_{2}, L_{2}).”

This would be more in the style of Definition 6.6 for ≲_{P3}, and would also avoid the singular behavior of the first alternative condition of Definition 6.12, and so offer continuity advantages.^{31} Moreover, for ≲_{CP0} instead of ≲_{CP1}, items 1 and 2 (but not item 3) of Corollary 6.13 still hold, as well as Theorem 6.14 and its Corollary 6.15. Furthermore, we get ≲_{CP0} ⊆ ≲_{CP1}. It is fatal for ≲_{CP0}, however, that this subset relation may be proper. For instance, ≲_{CP0} does not in general satisfy Theorem 6.16. Even worse, ≲_{CP0} does not show the proper behavior of ≲_{CP1} in Example 3.1 of § 3, as discussed in Example 6.17 of § 6.6: We get (∅, ¬flies(edna)) △_{CP0} (A_{2}, flies(edna)) instead of (∅, ¬flies(edna)) <_{CP1} (A_{2}, flies(edna)).

This can be seen by considering the activation set ∅ for (∅, ¬flies(edna)), which is not an activation set for (A_{2}, flies(edna)).

Such a behavior is obviously unacceptable in practice, and so we do not think that it makes sense to consider ≲_{CP0} any further.

Example 6.19 (continuing Example 3.2 of § 3) We have (A_{2}, flies(edna)) ≴_{CP1} (A_{1}, ¬flies(edna)) because flies(edna) ∉ �_{Π_{3.2}} and because {bird(edna)} ⊆ �_{Π_{3.2}} is an activation set for (A_{2}, flies(edna)), but not for (A_{1}, ¬flies(edna)).

We have (A_{1}, ¬flies(edna)) ≲_{P3} (A_{2}, flies(edna)), because flies(edna) ∉ �_{Π_{3.2}} and because, if H ⊆ �_{Π_{3.2}∪Δ_{3.2}} is a simplified activation set for (A_{1}, ¬flies(edna)), but not for (∅, ¬flies(edna)), then we have emu(edna) ∈ H, and thus H is a simplified activation set also for (A_{2}, flies(edna)).

31Cf. the discussion of such a continuity advantage in § 7.1 for the monotonicity w.r.t. conjunction.

All in all, by Theorem 6.16, we get (A_{1}, ¬flies(edna))<_{CP1}(A_{2}, flies(edna)) and (A_{1}, ¬flies(edna)) <_{P3} (A_{2}, flies(edna)).

Example 6.20  (continuing Example 3.3 of § 3)

We have (A_{2}, flies(edna)) ≲_{CP1} (A_{1}, ¬flies(edna)) because ¬flies(edna) ∉ �_{Π_{3.3}} and, for every activation set H ⊆ �_{Π_{3.3}} for (A_{2}, flies(edna)), we get emu(edna) ∈ H, and so H is an activation set also for (A_{1}, ¬flies(edna)).

Nevertheless, we have (A_{2}, flies(edna)) ≴_{P3} (A_{1}, ¬flies(edna)), because {bird(edna)} ⊆ �_{Π_{3.3}∪Δ_{3.3}} is a simplified activation set for (A_{2}, flies(edna)), but neither for (∅, flies(edna)), nor for (A_{1}, ¬flies(edna)).

We have (A_{1}, ¬flies(edna)) ≲_{P3} (A_{2}, flies(edna)), because of flies(edna) ∉ �_{Π_{3.3}} and because, if H ⊆ �_{Π_{3.3}∪Δ_{3.3}} is a simplified activation set for (A_{1}, ¬flies(edna)), but not for (∅, ¬flies(edna)), then we have emu(edna) ∈ H and thus H is a simplified activation set also for (A_{2}, flies(edna)).

All in all, by Theorem 6.16, we get (A_{1}, ¬flies(edna))≈_{CP1}(A_{2}, flies(edna)) and (A_{1}, ¬flies(edna)) <_{P3} (A_{2}, flies(edna)).

From a conceptual point of view, we have to ask ourselves, whether we would like the two defeasible rule instances in A_{2} = { flies(edna)←bird(edna), bird(edna)←emu(edna) } to reduce the specificity of (A_{2}, flies(edna)) as compared to a system that seems equivalent for the given argument for flies(edna), namely the argument ({flies(edna)←emu(edna)}, flies(edna)).

Does the specificity of a defeasible reasoning step really reduce if we introduce intermediate literals (such as bird(edna) between flies(edna) and emu(edna)) ?

According to human intuition, this question has a negative answer, as we have already explained in Remark 4.2 at the end of § 4.4.5.^{32}

Example 6.21  (continuing Example 3.4 of § 3)

We have (A_{2}, lovely)≴_{CP1}(A_{1}, ¬lovely) because lovely ∉ �_{Π_{3.4}} and because {somebody} ⊆ �_{Π_{3.4}} is an activation set for (A_{2}, lovely), but not for (A_{1}, ¬lovely).

We have (A_{1}, ¬lovely)≲_{P3}(A_{2}, lovely) because of lovely ∉ �_{Π_{3.4}} and because, if H ⊆ �_{Π_{3.4}∪Δ_{3.4}} is a simplified activation set for (A_{1}, ¬lovely), but not for (∅, ¬lovely), then we have {somebody, noisy} ⊆ H, and so H is also a simplified activation set for (A_{2}, lovely).

All in all, by Theorem 6.16, we get (A_{1}, ¬lovely)<_{CP1}(A_{2}, lovely) and (A_{1}, ¬lovely) <_{P3} (A_{2}, lovely).

Note that we can nicely see here that the condition that H is not a simplified activation set for (∅, ¬lovely) is relevant in Definition 6.6. Without this condition we would have to consider the simplified activation set {grandpa} for (A_{1}, ¬lovely), which is not an activation set for (A_{2}, lovely); and so, contrary to our intuition, (A_{1}, ¬lovely) would not be more specific than (A_{2}, lovely) w.r.t. ≲_{P3} anymore.

32Moreover, Examples 7.1 and 7.2 will exhibit a strong reason to deny this question: the requirement of monotonicity w.r.t. conjunction. Furthermore, see Example 7.3 for another example that makes even clearer why defeasible rules should be considered for their global semantical effect instead of their syntactical fine structure.

Example 6.22 (continuing Example 6.9 of § 6.2) The following holds for our specification of Example 6.9 by Lemma 6.10 and Corollary 6.8:

(A_{1}, Propose) <_{P3} (A_{2}, Kiss) <_{P3} (A_{3}, Smile) ≵_{P3} (A_{1}, Propose).

For our corrected relation CP1 we have:

(A_{1}, Propose) <_{CP1} (A_{2}, Kiss) <_{CP1} (A_{3}, Smile) >_{CP1} (A_{1}, Propose)

simply because the trouble-making set { Bold, Promising(Jo) } is not to be considered here. Indeed, this set is not a subset of �_{Π_{6.9}}. The checking of the details is left to the reader. Note that, because of Lemma 6.10, Theorem 6.16, Theorem 6.14, and Corollary 2.10, all that is actually left to show is

(A_{1}, Propose) ≵_{CP1} (A_{2}, Kiss) ≵_{CP1} (A_{3}, Smile).

7 Putting Specificity to Test w.r.t. Human Intuition

Before we will go on with further conceptual material and efficiency considerations in § 8, let us put our two main notions of specificity — as formalized in the two binary relations ≲_{P3} and ≲_{CP1} — to test w.r.t. our changed phase 1 of § 6.1 in a series of further examples.

Note that we can freely draw the consequence ≲_{P3} ⊆ ≲_{CP1} of Theorem 6.16 because at least one^{33} of its conditions is satisfied in all the following examples except Example 7.5, which is the only example in § 7 with an activation set that actually is not a simplified one.

Besides freely applying Theorem 6.16 — to enable the reader to make his own selection of interesting examples — we are pretty explicit in all of the following examples.

7.1 Monotonicity of the Specificity Relations w.r.t. Conjunction

Monotonicity w.r.t. conjunction is the following property for a binary relation R on argu-

ments: In case of  (A_{1}^{i}, L_{1}^{i}) R (A_{2}^{i}, L_{2}^{i})  for i ∈ {1, 2}, we always have (A_{1}^{1}∪A_{1}^{2}, L′_{1}) R (A_{2}^{1}∪A_{2}^{2}, L′_{2})

for fresh constant literals L′_{j} with rules L′_{j}⇐L_{j}^{1}∧L_{j}^{2} added to the general rules Π^{G} (j ∈ {1, 2}). In this case, we will call (A_{j}^{1}∪A_{j}^{2}, L′_{1}) the conjunction of the arguments (A_{j}^{1}, L_{j}^{1}) and (A_{j}^{2}, L_{j}^{2}).

This property is obviously given for ≲_{CP1} in case of L_{1}^{1}, L_{1}^{2} ∈ �_{Π} (which implies L′_{1} ∈ �_{Π}) and also in case of L_{1}^{1}, L_{1}^{2} ∉ �_{Π} (where we get L_{2}^{1}, L_{2}^{2}, L′_{1}, L′_{2} ∉ �_{Π} and just take the union of the two activation sets). Note that the latter case — where both arguments are defeasible — is certainly the most important one.

For the remaining borderline case of L_{1}^{i} ∉ �_{Π} ∋ L_{1}^{3−i} (for some i ∈ {1, 2}), however, monotonicity cannot be expected in general for ≲_{CP1}, simply because then we get L′_{1} ∉ �_{Π}, but do not necessarily have any activation set for L_{2}^{3−i}. This non-monotonicity, however, is part and parcel of our decision to prefer arguments whose literals are elements of �_{Π}, as expressed in item 1 of Definition 6.12 of § 6.4. As explained in Remark 6.18 of § 6.6, there does not seem to be an alternative to this technically required preference.

For ≲_{P1}, however, monotonicity is not even given for the case we just realized to be the most important one. This was already noted in [Poole, 1985], using the following example.

33Condition 4 of Theorem 6.16 is satisfied for Examples 3.2, 3.3, 3.4, and 7.7. Condition 3 (but not condition 4) is satisfied for Examples 7.1, 7.2, 7.3, 7.4 and 7.6.

33

Example 7.1 (Example 6 of [Poole, 1985])

Π_{7.1}^{F} := { a, d } ,
Π_{7.1}^{G} := \{ \begin{matrix}g_{1} ⇐ ¬c∧¬f, \\ g_{2} ⇐ c∧f \end{matrix} \} ,
Δ_{7.1} := A_{1} ∪ A_{2}.
A_{1} := \{ \begin{matrix}¬c ← a, \\ ¬f ← d \end{matrix} \}.

A_{2} := \{ \begin{matrix}b ← a, \\ c ← b, \\ e ← d, \\ f ← e \end{matrix} \}.

g_{1}

g_{2}

¬c  c  f  ¬f

b  e

\underline{\underline{a}}  \underline{\underline{d}} A1 A1 A2 A2 A2 A2

Let us compare the specificity of the arguments (A_{1}, g_{1}) and (A_{2}, g_{2}).

We have (A_{1}, g_{1}) ≈_{CP1} (A_{2}, g_{2}) because H ⊆ �_{Π_{7.1}} = {a, d} is an activation set for (A_{i}, g_{i}) if and only if H = {a, d}.

We have (A_{1}, g_{1}) △_{P3} (A_{2}, g_{2}) for the following reasons: {a, ¬f} ⊆ �_{Π_{7.1}∪Δ_{7.1}} is a simplified activation set for (A_{1}, g_{1}), but neither for (∅, g_{1}), nor for (A_{2}, g_{2}). {a, f} ⊆ �_{Π_{7.1}∪Δ_{7.1}} is a simplified activation set for (A_{2}, g_{2}), but neither for (∅, g_{2}), nor for (A_{1}, g_{1}).

Poole [1985] considers the same result for ≲_{P1} as for ≲_{P3} to be “seemingly unintuitive”, because, as we have seen for the isomorphic sub-specification in Example 3.3 of § 3, we have both (A_{1}, ¬c) <_{P3} (A_{2}, c) and (A_{1}, ¬f) <_{P3} (A_{2}, f).

Indeed, as already listed as an essential requirement in § 5, the conjunction of two respectively more specific derivations should be more specific.

On the other hand, considering ≲_{CP1} instead of ≲_{P3}, the conjunctions of two respective arguments that are pairwise equivalently specific are equivalently specific — exactly as one intuitively expects.

By turning the defeasible rule b←a of Example 7.1 into a strict general rule, we obtain the following example.

Example 7.2 (1^{st} Variation of Example 7.1)

Π_{7.2}^{F} := { a, d } ,
Π_{7.2}^{G} := \{ \begin{matrix}g_{1} ⇐ ¬c∧¬f, \\ g_{2} ⇐ c∧f, \\ b ⇐ a \end{matrix} \} ,
Δ_{7.2} := A_{1} ∪ A_{2}.
A_{1} := \{ \begin{matrix}¬c ← a, \\ ¬f ← d \end{matrix} \}.
A_{2} := \{ \begin{matrix}c ← b, \\ e ← d, \\ f ← e \end{matrix} \}.

g_{1}

g_{2}

¬c  c  f  ¬f

b  e

\underline{\underline{a}}  \underline{\underline{d}} A1 A1 A2 A2 A2

Let us compare the specificity of the arguments (A_{1}, g_{1}) and (A_{2}, g_{2}).

We have (A_{2}, g_{2}) ≴_{CP1} (A_{1}, g_{1}) because {b, d} ⊆ �_{Π_{7.2}} = {a, b, d} is an activation set for (A_{2}, g_{2}), but not for (A_{1}, g_{1}).

We have (A_{1}, g_{1}) ≲_{CP1} (A_{2}, g_{2}) because, for every activation set H ⊆ �_{Π_{7.2}} for (A_{1}, g_{1}), we have {a, d} ⊆ H; and so H is also an activation set for (A_{2}, g_{2}).

We again have (A_{1}, g_{1}) △_{P3} (A_{2}, g_{2}), for the same reason as in Example 7.1. Thus, the situation for ≲_{P3} is just as in Example 7.1, and just as “seemingly unintuitive” for exactly the same reason.

We have (A_{1}, g_{1}) <_{CP1} (A_{2}, g_{2}), which is intuitively correct because the conjunction of a more specific and an equivalently specific argument, respectively, should be more specific. Indeed, from the isomorphic sub-specifications in Examples 3.2 and 3.3, we know that (A_{1}, ¬c) <_{CP1} (A_{2}, c) and (A_{1}, ¬f) ≈_{CP1} (A_{2}, f), respectively.

All in all, the relation ≲_{P3} fails in this example again, whereas the quasi-ordering ≲_{CP1} works according to human intuition and satisfies monotonicity w.r.t. conjunction.

7.2 Implementation of the Preference of the “More Precise”

As primary sources of differences in specificity, all previous examples — except Example 3.4 of § 3, continued in Example 6.21 of § 6.6 — illustrate only the effect of chains of implications. According to our motivating discussion of § 4.4.5, we should consider also examples where the primary source of differences in specificity is an essentially required condition that is a super-conjunction of the condition triggering another rule. We will do so in the following examples.

As we have already shown in Example 6.21, both relations ≲_{P3} and ≲_{CP1} produce the intuitive result if the “more precise” super-conjunction is directly the condition of a rule. Let us see whether this is also the case if the condition of the rule is derived from a superconjunction.

By removing the second condition literal ¬f in the strict general rule g_{1}⇐¬c∧¬f of Example 7.1, we obtain the following example.

Example 7.3 (2^{nd} Variation of Example 7.1)

Π_{7.3}^{F} := { a, d } ,
Π_{7.3}^{G} := \{ \begin{matrix}g_{1} ⇐ ¬c, \\ g_{2} ⇐ c∧f \end{matrix} \} ,
Δ_{7.3} := A_{1} ∪ A_{2}.
A_{1} := { ¬c ← a }.

A_{2} := \{ \begin{matrix}b ← a, \\ c ← b, \\ e ← d, \\ f ← e \end{matrix} \}.

g_{1}  g_{2}

¬c  c  f

b  e

\underline{\underline{a}}  \underline{\underline{d}} A1 A2 A2 A2 A2

Let us compare the specificity of the arguments (A_{1}, g_{1}) and (A_{2}, g_{2}).

We have (A_{1}, g_{1}) ≴_{CP1} (A_{2}, g_{2}) because {a} ⊆ �_{Π_{7.3}} = {a, d} is an activation set for (A_{1}, g_{1}), but not for (A_{2}, g_{2}).

We have (A_{2}, g_{2}) ≲_{CP1} (A_{1}, g_{1}) because any activation set for (A_{2}, g_{2}) that is a subset of �_{Π_{7.3}} includes a, and so is also an activation set for (A_{1}, g_{1}).

Considering Theorem 6.16 as well as the the activation set {b, d} for (A_{2}, g_{2}),

we get  (A_{1}, g_{1}) △_{P3} (A_{2}, g_{2}),
contrary to (A_{1}, g_{1}) >_{CP1} (A_{2}, g_{2}).

Thus, ≲_{CP1} realizes the intuition that the super-conjunction a∧d — which is essential to derive c∧f according to A_{2} — is more specific than the “less precise” a.

Just like Example 6.20 of § 6.6, this example shows again that ≲_{P3} does not properly implement the intuition that — in a model-theoretic approach to specificity — defeasible rules should be considered for their global semantical effect instead of their syntactical fine structure.

Example 7.4 (Example 11 from [Stolzenburg &al., 2003, p. 96])

Π_{7.4}^{F} := { c, d, e } ,
Π_{7.4}^{G} := { x ⇐ a∧f } ,
Δ_{7.4} := A^{1} ∪ A^{2} ∪ A^{3} ∪ A^{4} ∪ A^{5}.
A^{1} := { x ← a∧b∧c }.
A^{2} := { ¬x ← a∧b }.
A^{3} := { f ← e }.

\begin{aligned}A^{4} & := & \{ a ← d \} . \\ A^{5} & := & \{ b ← e \} . \end{aligned}

x  x

¬x

a  b  f

\underline{\underline{d}}  \underline{\underline{c}}  \underline{\underline{e}} A1 A1 A1 A2 A2 A3 A4 A5

Compare the specificity of the arguments (A^{1}∪A^{4}∪A^{5}, x), (A^{2}∪A^{4}∪A^{5}, ¬x), (A^{3}∪A^{4}, x) !

We have (A^{1}∪A^{4}∪A^{5}, x) <_{CP1} (A^{2}∪A^{4}∪A^{5}, ¬x) ≈_{CP1} (A^{3}∪A^{4}, x), because of x, ¬x ∉ �_{Π_{7.4}}, and because any activation set H ⊆ �_{Π_{7.4}} = {c, d, e} for any of (A^{1}∪A^{4}∪A^{5}, x), (A^{2}∪A^{4}∪A^{5}, ¬x), (A^{3}∪A^{4}, x) contains {d, e}, which is an activation set only for the latter two.

This matches our intuition well, because the first of these arguments essentially requires the “more precise” c∧d∧e instead of the less specific d∧e.

We have (A^{1}∪A^{4}∪A^{5}, x) △_{P3} (A^{2}∪A^{4}∪A^{5}, ¬x) △_{P3} (A^{3}∪A^{4}, x) △_{P3} (A^{1}∪A^{4}∪A^{5}, x), however.^{34} This means that ≲_{P3} cannot compare these counterarguments and cannot help us to pick the more specific argument.

What is most interesting under the computational aspect is that, for realizing

(A^{1}∪A^{4}∪A^{5}, x) ≴_{P3} (A^{2}∪A^{4}∪A^{5}, ¬x),

we have to consider the simplified activation set {d, f} ⊆ �_{Π_{7.4}∪Δ_{7.4}} for (A^{1}∪A^{4}∪A^{5}, x). This means that here — to realize that f ∈ �_{Π_{7.4}∪Δ_{7.4}} — we have to take into account the defeasible rule of A^{3}, which is not part of any of the two arguments under comparison.^{35}

Note that such considerations are not required, however, for realizing the properties of ≲_{CP1}, because defeasible rules not in the given argument can be completely ignored when calculating the minimal activation sets as subsets of �_{Π} instead of �_{Π∪Δ}. In particular, the complication of pruning — as discussed in detail in [Stolzenburg &al., 2003, § 3.3] — does not have to be considered for the operationalization of ≲_{CP1}.

34Because {d, f} ⊆ �_{Π_{7.4}∪Δ_{7.4}} is a simplified activation set for (A^{4}, x), but neither for (∅, x), nor for (A^{2}∪A^{4}∪A^{5}, ¬x), we have (A^{1}∪A^{4}∪A^{5}, x) ≴_{P3} (A^{2}∪A^{4}∪A^{5}, ¬x) ≵_{P3} (A^{3}∪A^{4}, x).

Because of (A^{3}∪A^{4}, x) ≴_{CP1} (A^{1}∪A^{4}∪A^{5}, x) ≵_{CP1} (A^{2}∪A^{4}∪A^{5}, ¬x), we have (A^{3}∪A^{4}, x) ≴_{P3} (A^{1}∪A^{4}∪A^{5}, x) ≵_{P3} (A^{2}∪A^{4}∪A^{5}, ¬x)

by Theorem 6.16. Because {b, c, d} ⊆ �_{Π_{7.4}∪Δ_{7.4}} is a simplified activation set for (A^{2}∪A^{4}∪A^{5}, ¬x) and (A^{1}∪A^{4}∪A^{5}, x), but for none of (∅, ¬x), (∅, x), (A^{3}∪A^{4}, x), we have

(A^{2}∪A^{4}∪A^{5}, ¬x) ≴_{P3} (A^{3}∪A^{4}, x) ≵_{P3} (A^{1}∪A^{4}∪A^{5}, x).

35Have a look at Figure 1 in § 6.1 to see that the effect of f proceeds here only via the set F , but not via the usage of the set H at the bottom of Figure 1.

By turning the defeasible rule f←e of Example 7.4 into a strict general rule, we obtain the following example.

Example 7.5 (Variation of Example 7.4)

Π_{7.5}^{F} := { c, d, e } ,
Π_{7.5}^{G} := \{ \begin{matrix}x ⇐ a∧f, \\ f ⇐ e \end{matrix} \} ,
Δ_{7.5} := A^{1} ∪ A^{2} ∪ A^{4} ∪ A^{5},
A^{1} := { x ← a∧b∧c }.
A^{2} := { ¬x ← a∧b }.
A^{4} := { a ← d } ,
A^{5} := { b ← e } .

x  x

¬x

a  b  f

\underline{\underline{d}}  \underline{\underline{c}}  \underline{\underline{e}} A1 A1 A1 A2 A2 A4 A5

Compare the specificity of the arguments (A^{1}∪A^{4}∪A^{5}, x), (A^{2}∪A^{4}∪A^{5}, ¬x), (A^{4}, x) !

Obviously, x, ¬x ∉ �_{Π_{7.5}} = {c, d, e, f}. Moreover, {d} ⊆ �_{Π_{7.5}} is an activation set for (A^{4}, x) (but not a simplified one!) and, a fortiori (by Corollary 6.13(1)), for (A^{1}∪A^{4}∪A^{5}, x), but not for (A^{2}∪A^{4}∪A^{5}, ¬x). Furthermore, every activation set H ⊆ �_{Π_{7.5}} for (A^{2}∪A^{4}∪A^{5}, ¬x) satisfies {d, e} ⊆ H, which is an activation set for (A^{4}, x) and (A^{1}∪A^{4}∪A^{5}, x). Finally, every activation set H ⊆ �_{Π_{7.5}} for (A^{1}∪A^{4}∪A^{5}, x) satisfies {d} ⊆ H which is an activation set for (A^{4}, x).

All in all, we have (A^{4}, x) ≈_{CP1} (A^{1}∪A^{4}∪A^{5}, x) >_{CP1} (A^{2}∪A^{4}∪A^{5}, ¬x).

This is intuitively sound because (A^{2}∪A^{4}∪A^{5}, ¬x) is activated only by the more specific d∧e, whereas (A^{4}, x) is activated also by the “less precise” d.

Moreover, c∧d∧e is not essentially required for (A^{1}∪A^{4}∪A^{5}, x), and so this argument is tantamount to (A^{4}, x). The reason for this remarkable effect is not the lack of minimality of the argument (A^{1}∪A^{4}∪A^{5}, x), but our semantical, model-theoretic approach, which simply ignores the fact that the derivation via A^{1} requires the more precise activation set. Indeed, we primarily consider consequence, not derivation.

We have (A^{4}, x) <_{P3} (A^{1}∪A^{4}∪A^{5}, x) △_{P3} (A^{2}∪A^{4}∪A^{5}, ¬x) △_{P3} (A^{4}, x), however.^{36} This means that ≲_{P3} fails here completely w.r.t. Poole’s intuition, as actually in most

non-trivial examples.

7.3 Conflict between the “More Concise” and the “More Precise”

By removing the second condition literal ¬f in the strict general rule g_{1}⇐¬c∧¬f of Example 7.2, we obtain the following example.

36The minimal simplified activation sets for (A^{4}, x) that are no simplified activation sets for (∅, x) are {d, e} and {d, f}. The minimal simplified activation sets for (A^{1}∪A^{4}∪A^{5}, x) that are no simplified activation sets for (∅, x) are {d, e}, {d, f}, {a, b, c}, and {b, c, d}. The minimal simplified activation sets for (A^{2}∪A^{4}∪A^{5}, ¬x) that are no simplified activation sets for (∅, ¬x) are {a, b}, {a, e}, {b, d}, and {d, e}.

37

Example 7.6 (Variation of Example 7.2)

Π_{7.6}^{F} := { a, d } ,
Π_{7.6}^{G} := \{ \begin{matrix}g_{1} ⇐ ¬c, \\ g_{2} ⇐ c∧f, \\ b ⇐ a \end{matrix} \} ,
Δ_{7.6} := A_{1} ∪ A_{2}.
A_{1} := { ¬c ← a }.
A_{2} := \{ \begin{matrix}c ← b, \\ e ← d, \\ f ← e \end{matrix} \}.

g_{1}  g_{2}

¬c  c  f

b  e

\underline{\underline{a}}  \underline{\underline{d}} A1 A2 A2 A2

Let us compare the specificity of the arguments (A_{1}, g_{1}) and (A_{2}, g_{2}).

We have (A_{1}, g_{1}) △_{CP1} (A_{2}, g_{2}) for the following reasons: {a} ⊆ �_{Π_{7.6}} = {a, b, d} is an activation set for for (A_{1}, g_{1}), but not for (A_{1}, g_{1}); {b, d} ⊆ �_{Π_{7.6}} is an activation set for (A_{2}, g_{2}), but not for (A_{2}, g_{2}).

By Theorem 6.16 we also get (A_{1}, g_{1}) △_{P3} (A_{2}, g_{2}).

In this example the two intuitive reasons for specificity — super-conjunction (preference of the “more precise”) and implication via a strict rule (preference of the “more concise”) — are in an irresolvable conflict, which goes well together with the fact that neither ≲_{CP1} nor ≲_{P3} can compare the two arguments.

7.4 Global Effect matters more than Fine Structure

The following example nicely shows that any notion of specificity based only on single defeasible rules (without considering the context of the general strict rules as a whole) cannot be intuitively adequate.

Example 7.7 (Example from Page 95 of [Stolzenburg &al., 2003])

Π_{7.7}^{F} := { q(a) } ,
Π_{7.7}^{G} := { s(x) ⇐ q(x) } ,
Δ_{7.7} := \{ \begin{matrix}p(x) ← q(x), \\ ¬p(x) ← q(x)∧s(x) \end{matrix} \} ,
A_{1} := { ¬p(a) ← q(a)∧s(a) },
A_{2} := { p(a) ← q(a) }

¬p(a)  p(a)

s(a)

\underline{\underline{q(a)}} A1 A1 A2

Let us compare the specificity of the arguments (A_{1}, ¬p(a)) and (A_{2}, p(a)).

We have (A_{1}, ¬p(a)) ≈_{P3} (A_{2}, p(a)), because of p(a), ¬p(a) ∉ �_{Π_{7.7}} = {q(a), s(a)}, and because, for H ⊆ �_{Π_{7.7}∪Δ_{7.7}}, i ∈ {1, 2}, L_{1} := ¬p(a), and L_{2} := p(a), we have the logical equivalence of H = {q(a)} on the one hand, and of H being a minimal simplified activation set for (A_{i}, L_{i}) but not for (∅, L_{i}), on the other hand.

By Theorem 6.16, we also get (A_{1}, ¬p(a)) ≈_{CP1} (A_{2}, p(a)).

This makes perfect sense because q(a)∧ s(a) is not at all strictly “more precise” than q(a) in the context of Π_{7.7}^{G}.

Note that nothing is changed here if s(x) ⇐ q(x) is replaced by setting Π_{7.7}^{G} := {s(a)}. If s(x) ⇐ q(x) is replaced by setting Π_{7.7}^{G} := ∅ and Π_{7.7}^{F} := {q(a), s(a)}, however, then we get both (A_{1}, ¬p(a)) <_{P3} (A_{2}, p(a)) and (A_{1}, ¬p(a)) <_{CP1} (A_{2}, p(a)).

This also speaks for our admission of literals (i.e. unconditional rules) to Π^{G}.^{37}

8 Efficiency Considerations and the Specificity Ordering CP2

The specificity relations P1, P2, P3, and CP1^{38} share several efficiency features, which we will highlight in this section. Moreover, we will introduce the specificity ordering CP2, a minor variation of CP1 toward more efficiency and intuitive adequacy. Finally, we will discuss further steps toward more efficiency following Herbrand’s Fundamental Theorem.

8.1 A Slight Gain in Efficiency

A straightforward procedure toward deciding the specificity relations ≲_{CP1} and ≲_{P3} between two arguments is to consider all possible activation sets from the literals in the sets �_{Π} and �_{Π∪Δ}, respectively. The effort for computing ≲_{CP1} is lower than that of ≲_{P3} because of �_{Π} ⊆ �_{Π∪Δ}, though not w.r.t. asymptotic complexity: In both cases already the number of possible (simplified) activation sets is exponential in the number of literals in the respective sets �_{Π} and �_{Π∪Δ}, because each possible subset has to be tested

8.2 Comparing Derivations

To lower the computational complexity, more syntactic criteria for computing specificity were introduced in [Stolzenburg &al., 2003]. These criteria refer to the derivations for the given arguments. More precisely, they refer to the and-trees of Definition 4.1 in § 4.4.1.

8.2.1 No Pruning Required

The concept of pruning and-trees is introduced in [Stolzenburg &al., 2003, Definition 12] in this context, because, for the case of ≲_{P2}, attention cannot be restricted to derivations which make use only of the instances of defeasible rules given in the arguments. The reason for this is that the specificity notions according to [Poole, 1985] and [Simari & Loui, 1992] admit literals L in activation sets that cannot be derived solely by strict rules, i.e. L ∈ �_{Π∪Δ}\�_{Π}. Since this is not possible with the relation ≲_{CP1}, this problem vanishes with our corrected version of specificity. This problem and its vanishing are discussed in Example 7.4 of § 7.2.

8.2.2 Sets of Derivations have to be Compared

Yet still, the specificity relation ≲_{CP1} inherits several properties from ≲_{P3}. For instance, the syntactic criteria of their definitions require us in general to compare two sets of derivations element by element. This is true for both specificity relations, as shown in the following example.

37Cf. Note 3 of § 2.3.

38P1 follows [Poole, 1985] and can be found in this paper in Definition 6.3 of § 6.2. P2 follows [Simari & Loui, 1992] and can be found in Definition 6.4 of § 6.2. P3 respects non-defeasible arguments and can be found in Definition 6.6 of § 6.2. CP1 is our transitive relation found in Definition 6.12 of § 6.4.

39

Example 8.1 (Minimal argument with two minimal and-trees/activation sets)

Π_{8.1}^{F} := { b, c, d } ,
Π_{8.1}^{G} := \{ \begin{matrix}f ⇐ c∧e, \\ f ⇐ d∧e, \\ g ⇐ d∧e, \end{matrix} \} ,
Δ_{8.1} := A_{1} ∪ A_{2}.
A_{1} := \{ \begin{matrix}¬h ← g, \\ e ← b \end{matrix} \} .
A_{2} := \{ \begin{matrix}h ← f, \\ e ← b \end{matrix} \} .

¬h  h

g  f  f

\underline{\underline{d}}  e  \underline{\underline{c}}

\underline{\underline{b}} A1 A2 A1∩A2

The argument (A_{1}, ¬h) has {b, d} as the only minimal activation set that is a subset of �_{Π_{8.1}} = Π_{8.1}^{F}. {b, d} is also a minimal activation set for (A_{2}, h). On the other hand, {b, c} is an activation set for (A_{2}, h), but not for (A_{1}, ¬h). Thus, we get (A_{1}, ¬h) <_{CP1} (A_{2}, h).

Because either d or c is in an and-tree of the argument (A_{2}, h) (but never both!), a comparison of two fixed and-trees does not suffice.

Moreover note that we have (A_{1}, ¬h) △_{P3} (A_{2}, h), because of the simplified activation sets {g} and {f}, respectively.

Furthermore note that the only minimal activation set for the minimal argument ({e←b}, f) is {b}, which, however, is not a simplified activation set for that argument.

The reason for the complication of an element-by-element comparison of and-trees is that we consider a very general setting of defeasible reasoning in this paper. Indeed, we admit

1. more than one condition literal in rules, i.e. conditions containing more than one literal, and

2. non-empty sets of background knowledge, i.e. general rules, not only facts.

Typically, only restricted cases are considered: Conditions have always to be singletons in [Gelfond & Przymusinska, 1990], no background knowledge is allowed in [Dung & Son, 1996], and both restrictions are present in [Benferhat & Garcia, 1997].

8.2.3 Path Criteria?

Before we come to the computation of activations sets via goal-directed derivations in § 8.3, let us have a closer look here at the path criterion of [Stolzenburg &al., 2003, § 3.4].

Definition 8.2 (Path) For a leaf node N in an and-tree T, we define the path in T through N as the empty set if N is the root, and otherwise as the set consisting of the literal labeling N, together with all literals labeling its ancestors except the root node. Let Paths(T) be the set of all paths in T through all leaf nodes N.

With this notion of paths, the quasi-ordering ⊴ on and-trees can be given as follows:

Definition 8.3 ([Stolzenburg &al., 2003, Definition 23]) T_{1} ⊴ T_{2} if T_{1} and T_{2} are two and-trees, and for each t_{2} ∈ Paths(T_{2}) there is a path t_{1} ∈ Paths(T_{1}) such that t_{1} ⊆ t_{2}.

Two and-trees can be compared w.r.t. ⊴ efficiently. This requires the subset comparison of all paths of the two trees, respectively. Hence, the respective complexity is polynomial, at most O(n^{3}), where n is the overall number of nodes in the and-trees.^{39} This made the relation ⊴ attractive for practical use in the context of [Stolzenburg &al., 2003] compared to the exponential comparison mention in § 8.1. As stated in the following definition, for a comparison of specificity we have to consider all and-trees, however, and so we still remain with an overall exponential time complexity, which is not better than the one we will describe in Remark 8.28 of § 8.3.4.

Definition 8.4 ([Stolzenburg &al., 2003, Definition 24]) (A_{1}, h_{1}) ≤ (A_{2}, h_{2}) if (A_{1}, h_{1}) and (A_{2}, h_{2}) are two arguments in the given specification and for each and-tree T_{1} for h_{1} there is an and-tree T_{2} for h_{2} such that T_{1} ⊴ T_{2}.

It is shown in [Stolzenburg &al., 2003, Theorem 25] that ≤ and ≲_{P2} are equal in special cases, namely if the arguments involved in the comparison correspond to exactly one and-tree. Let us try to adapt this result to our new relation ≲_{CP1}, in the sense that we try to establish a mutual subset relation between ≤ and ≲_{CP1}.

The forward direction is pretty straightforward, but comes with the restriction to be expected: From [Stolzenburg &al., 2003, Theorem 25] we get ≤ ⊆ ≲_{P2}. By looking at the empty path, we easily see that ≤ satisfies the additional restriction of Definition 6.6 as compared to Definition 6.4; so we also get ≤ ⊆ ≲_{P3}. Finally, we can apply Theorem 6.16 and get the intended ≤ ⊆ ≲_{CP1}, but only with the strong restriction of the condition of Theorem 6.16. We see no way yet to relax this restriction resulting from phase 3 of § 6.1.

It is even more unfortunate that the backward direction does not hold at all because of our change in phase 1 of § 6.1. In particular, as shown in the following example, it does not hold for the special case where it holds for ≲_{P2}, i.e. in the case that there are no general rules and hence each minimal argument corresponds to exactly one derivation (cf. the proof of Theorem 25 in [Stolzenburg &al., 2003]).

Example 8.5

Π_{8.5}^{F} := {a, b}, Π_{8.5}^{G} := ∅,
Δ_{8.5} := A_{1} ∪ A_{2}.
A_{1} := \{ \begin{matrix}c_{1} ← a∧b, \\ d ← c_{1} \end{matrix} \}.
A_{2} := \{ \begin{matrix}c_{2} ← a, \\ ¬d ← c_{2} \end{matrix} \}.

\begin{matrix}¬d & d \\ c_{2} & c_{1} \\ \underline{\underline{a}} & & \underline{\underline{b}} \end{matrix} ; A2 ; A2 ; A1 ; A1 ; A1

We have (A_{1}, d) △_{P3} (A_{2}, ¬d) and (A_{1}, d) <_{CP1} (A_{2}, ¬d).

Both arguments (A_{1}, d) and (A_{2}, ¬d) correspond to exactly one and-tree, say T_{1} and T_{2}, respectively. All paths in Paths(T_{1}) contain c_{1}, but not c_{2}, and all paths in Paths(T_{2}) contain c_{2}, but not c_{1}. Hence, (A_{1}, d) ≤ (A_{2}, ¬d) does not hold.

39To see this, note that the literals of the paths of the and-trees can be sorted, which reduces the complexity of the test for the subset property.

8.3 Toward a More Efficiently Realizable Notion of Poole-Style Specificity

Contrary to our small examples in the previous sections, examples of a practically relevant size require notions of specificity that can be decided efficiently.

As we are mainly interested in the more specific arguments, i.e. in the minimal elements of our specificity ordering, we may admit variations of our specificity ordering CP1 that offer better chances for an efficient implementation, but do not relevantly differ w.r.t. these minimal elements.

Therefore, in this section, we will introduce another correction (CP2) of Poole’s specificity relation, which offers some advantages for the computation of the respective activation sets, whereas our specificity ordering CP1 offers only the minor advantages over P1, P2, P3 we have already described in §§ 8.1 and 8.2.1.

More precisely, our plan for this section is to obtain another quasi-ordering ≲_{CP2} by slight modification of our quasi-ordering ≲_{CP1}, such that the two do not differ in any of our previous examples, and such that ≲_{CP2} may mirror our intuition on specificity according to the analysis in § 4 even more closely in some aspects. Finally, we will try to develop a more efficient procedure for deciding the specificity quasi-ordering ≲_{CP2} than those known for any of ≲_{P1}, ≲_{P2}, ≲_{P3}, ≲_{CP1}.

The crucial step in such a procedure is the computation of activation sets. For a goaldirected, SLD-resolution-like computation of activation sets we cannot keep our restriction to arguments that are ground. For this reason, we now have to modify our notion of a derivation by disallowing the instantiation of variables in our definition of �_{Π} and ⊢ (cf. Definition 2.3) as already hinted at in Remark 2.8 at the end of § 2.4. As a compensation, we then may add a hat over a set of rules Π, such that Π̂ denotes the set of all instances of Π.

8.3.1 Immediate Activation Sets

As a first step — since the workaround via path criteria failed in § 8.2.3 — we now have to find a new notion of an immediate activation set such that there are less^{40} and more easily computable immediate activation sets for a given argument than (non-immediate) activation sets according to Definition 6.1 of § 6.1. Our idea here is to avoid SLD-resolution steps that expand a goal clause by inessential applications of rules in the sense of the following definition, where we again apply the simple concept of an and-tree given in Definition 4.1 of § 4.4.1.

Definition 8.6 (Inessential Application of an Instance of a Rule) The application of the instance L⇐C of a rule in an and-tree is inessential (in the and-tree) if there is a node between the root (inclusively) and the application (including the node labeled with L) that is labeled with an element of �Π̂.

40There are indeed never more (cf. Corollary 8.8(4)), and typically much less immediate activation sets than activation sets.

As a step toward a more efficiently realizable notion of Poole-style specificity, we will now eliminate those activation sets from our considerations that rely on and-trees with an inessential application of the instance of a defeasible rule.^{41}

As a side effect, this step will also eliminate all redundant activation sets that result from what was called “growth of the defeasible parts toward the leaves” in § 4.4.3. This growth results from inessential application not of defeasible rules, but of general rules only. Contrary to the inessential application of instances of defeasible rules, this elimination of inessential applications of general rules will not change our specificity relation.

The positive effect, however, of cutting off this growth is the following. When the leaves of the defeasible part of an and-tree are included in �Π̂ for the first time in a root-to-leaves traversal, we immediately stop and obtain one single immediate activation set, and that’s it! The further enumeration of subsumed activation sets is no longer required.

While this reduction of the number of activation sets to one single immediate activation set for each and-tree is most helpful for the computation related to the first argument of the relation ≲_{CP2} when trying to decide it, for the computation related to the second argument it re-introduces the complication we already had in our first sketch of a notion of specificity in § 4.3.2, as compared to the simplified, second version of this sketch in § 4.4.4, which was the basis for our first formal definition of activation sets in Definition 6.1 of § 6.1.

This complication is only a notational one. It requires the notion of weakly immediate activation sets in addition to (non-weakly) immediate ones. This complication does not mean any extra-computation, not even for the second argument in the test for ≲_{CP2}: It is just so that the test whether every activation set of the first argument is subsumed by some activation set for the second argument becomes independent from the computation of activation sets. This independence has the advantage that we can optimize it in several directions: First of all, we must omit all rules from Π^{F} and Δ, which play some minor rôles in the computation of non-immediate activation sets (namely Π^{F} for acceptance as an activation set, and the instances of Δ that form the first element of the argument for expansion of activation sets). It is more important, however, that we may also add some forward reasoning from the activation set computed for the first argument in the test for ≲_{CP2}.

All in all, this means for our operationalization that the computation of activation sets (cf. Definition 6.1) has to be replaced with the computation of immediate activation sets according to the following definition, which also mirrors our isolation of defeasible parts of derivations in § 4.4.1 more directly than before, namely in the sense that a growth towards the leaves is avoided and the further dissection described in Note 7 of § 4.4.2 takes place.

It may be helpful for an intuitive understanding of the following definition to have a look at Figure 1 in § 6.1: The root tree depicted there is captured in item 2 of the following definition, its sub-trees in item 1.

41The first idea could be to take only activation sets all of whose literals occur in the condition of a rule in A, for the respective argument (A, L). This idea, however, is too restrictive because also general rules may play a rôle in the defeasible parts of the derivations, cf. § 4.4.1.

Definition 8.7 ([Minimal/Weakly] Immediate Activation Set) Let A be a set of instances of rules from Δ, and let L be a literal. H is an immediate activation set for (A, L) if H ⊆ �Π̂ and there is a (possibly empty) set of literals �, such that both of the following two items hold:

1. For each L′ ∈ �there is an and-tree for the derivation of H ∪A∪Π̂^{G} ⊢ {L′} in which

(a) the root is labeled with L′ and generated by an element of A, and
(b) every literal L′′ that labels a non-leaf node or the root satisfies L′′ ∉ �Π̂, and
(c) every literal L′′ ∉ A that labels a leaf node satisfies L′′ ∈ �Π̂,^{42}

such that the set of literals labeling the leaves of these trees is a subset of H ∪ �Π̂^{G} ∪A.

2. There is an and-tree for the derivation of �∪ Π̂ ⊢ {L}, such that each literal L′′ labeling a node in a path from the root to a leaf labeled with an element from � satisfies L′′ ∉ �Π̂.

H is a minimal immediate activation set for (A, L) if H is an immediate activation set for (A, L), but no proper subset of H is an immediate activation set for (A, L).

H is a weakly immediate activation set for (A, L) if H ⊆ �Π̂ and there is an immediate activation set H′ for (A, L) with H′ ⊆ �_{H∪Π̂^{G}}.

Corollary 8.8 Let A be a set of instances of rules from Δ, and let L be a literal.

1. If H is an [weakly] immediate activation set for (A, L), then we have H ⊆ �Π̂.

2. If H is a minimal immediate activation set for (A, L), then we have H ⊆ �Π̂ \ (�Π̂^{G} ∪ A).

3. Every immediate activation set for (A, L)

is a weakly immediate activation set for (A, L).

4. Every [weakly] immediate activation set for (A, L) is an activation set^{43} for (A, L).

5. Every minimal activation set for (A, L) that is an immediate activation set for (A, L) is a minimal immediate activation set for (A, L).

42Here “literal L′′ ∉ A” means that L′′ is a literal that is not a literal in A, i.e. no conclusion of an unconditional rule from A. Note that, by (a), this excludes any overlap of (b) and (c) (which would result in contradictory requirements): If the root is a leaf, then, by (a), it is labeled with a literal from A.

43Instead of the otherwise required condition that A is ground, we assume here — and will do so in what follows without further mentioning — that the definition of an activation set in Definition 6.1 of § 6.1 refers (just as Definition 8.7 of immediate ones and just as we have changed arguments and derivations in this section) to sets also of non-ground instances of defeasible rules in the first element of arguments, but with non-instantiating derivations and theories.

Remark 8.9 (Difference between an Activation Set and an Immediate one) Regarding the respective specificity orderings, an immediate activation set crucially differs from an activation set as follows: Certain defeasible parts may no longer participate in the derivation, namely those parts that derive a node labeled with an element of �Π̂. This means that those deviations which contain inessential (in the sense of Definition 8.6) applications of instances of defeasible rules can no longer increase the number of activation sets, i.e. can no longer reduce the specificity of an argument. We cannot see any reason why the fact that the first element of the argument may also be re-used to re-derive a literal of �Π̂ from �Π̂ should be relevant for the specificity of the argument. Therefore we think that this crucial difference (besides the omission of subsumed activation sets, which effects efficiency only) is in line with common intuition. Moreover, note that the crucial difference also admits the omission of all defeasible rules whose conclusion is part of the theory �Π̂ when computing immediate activations sets, which does not seem to be possible for (non-immediate) activation sets.

Definition 8.10 (≲_{CP2} : 2^{nd} Version of our Specificity Relation) (A_{1}, L_{1}) ≲_{CP2} (A_{2}, L_{2}) if (A_{1}, L_{1}) and (A_{2}, L_{2}) are arguments, and we have

1. L_{1} ∈ �Π̂ or

2. L_{2} ∉ �Π̂ and every H ⊆ �Π̂ that is an [minimal] immediate activation set for (A_{1}, L_{1}) is a weakly immediate activation set for (A_{2}, L_{2}).

To see that nothing essential has changed, compare the following Corollary 8.11 to Corollary 6.13 of § 6.4.

Corollary 8.11 If (A_{1}, L_{1}), (A_{2}, L_{2}) are arguments with A_{1} ⊆ A_{2}, then any of the following conditions is sufficient for (A_{1}, L_{1}) ≲_{CP2} (A_{2}, L_{2}) :

1. L_{1} = L_{2}.

2. L_{2} ∈ �Π̂ ⇒ L_{1} ∈ �Π̂ and {L_{1}} ∪ Π̂ ⊢ {L_{2}}.

3. L_{1} ∈ �Π̂ (which is implied by A_{1} = ∅ by Definition 2.7).

Remark 8.12 (Optional Minimality Restriction has No Effect) Note that the omission of the optional restriction to minimal immediate activation sets for (A_{1}, L_{1}) in Definition 8.10 has no effect on the extension of the defined notion. Proof: Suppose that L_{1}, L_{2} ∉ �Π̂, and that H′′ is an immediate activation set for (A_{1}, L_{1}). Because the related derivation is finite, we may assume that H′′ is finite w.l.o.g. Thus, there is a minimal immediate activation set H ⊆ H′′ for (A_{1}, L_{1}). If we now assume (A_{1}, L_{1}) ≲_{CP2} (A_{2}, L_{2}) with respect to a definition with the optional minimality restriction, then H is a weakly immediate activation set for (A_{2}, L_{2}), i.e. there is an immediate activation set H′ ⊆ �_{H∪Π̂^{G}} for (A_{2}, L_{2}), which (because of the monotonicity of our logic) implies H′ ⊆ �_{H′′∪Π̂^{G}}, i.e. H′′ is a weakly immediate activation set for (A_{2}, L_{2}) as well, as was to be shown.

Remark 8.13 (Relaxation to a Weakly immediate activation set is crucial) Note that we cannot straightforwardly require H to be a (non-weakly) immediate activation set for (A_{2}, L_{2}) in Definition 8.10, because otherwise our new relation CP2 would already fail to pass Example 3.2 of § 3, in the sense that both arguments there would be incomparable.^{44} ^{45}

Theorem 8.14 ≲_{CP2} is a quasi-ordering on arguments.

Proof of Theorem 8.14 ≲_{CP2} is a reflexive relation on arguments because of Corollary 8.11. To show transitivity, let us assume (A_{1}, L_{1}) ≲_{CP2} (A_{2}, L_{2}) and (A_{2}, L_{2}) ≲_{CP2} (A_{3}, L_{3}). According to Definition 8.10, because of (A_{1}, L_{1}) ≲_{CP2} (A_{2}, L_{2}), we have L_{1} ∈ �Π̂ — and then immediately the desired (A_{1}, L_{1}) ≲_{CP2} (A_{3}, L_{3}) — or we have L_{2} ∉ �Π̂. The latter case excludes the first option in Definition 8.10 as a justification for (A_{2}, L_{2}) ≲_{CP2} (A_{3}, L_{3}). Thus, it now suffices to consider the case that L_{i} ∉ �Π̂ for all i ∈ {1, 2, 3}. Suppose that H is an immediate activation set for (A_{1}, L_{1}). It suffices to show that H is a weakly immediate activation set for (A_{3}, L_{3}), i.e. to find an immediate activation set H′′ ⊆ �_{H∪Π̂^{G}} for (A_{3}, L_{3}). Because of our supposition, the first step of our original assumption, and the case considered, H is a weakly immediate activation set for (A_{2}, L_{2}), i.e. there is an immediate activation set H′ ⊆ �_{H∪Π̂^{G}} for (A_{2}, L_{2}). Then, because of the second step of our original assumption and the case considered, there is an immediate activation set H′′ ⊆ �_{H′∪Π̂^{G}} for (A_{3}, L_{3}). Because of the monotonicity of our logic and the closedness of our theories, we now have H′′ ⊆ �_{H′∪Π̂^{G}} ⊆ �_{�_{H∪Π̂^{G}}∪Π̂^{G}} = �_{H∪Π̂^{G}}, i.e. H′′ ⊆ �_{H∪Π̂^{G}}, as was to be shown.

Q.e.d. (Theorem 8.14)

Example 8.15 (≲_{CP1} vs. ≲_{CP2})

Π_{8.15}^{F} := { thirst, danger } , Π_{8.15}^{G} := ∅, Δ_{8.15} := A_{1} ∪ A_{3}.
A_{1} := { drink ← thirst }.
A_{2} := { alarm ← danger }.
A_{3} := A_{2} ∪ { danger ← thirst }.

drink alarm alarm

\underline{\underline{danger}}

\underline{\underline{thirst}} A1 A2 A3 A3

First note that — because of Π_{8.15}^{G} = ∅ — the two notions of an immediate and a weakly immediate activation set coincide here.

We have �Π̂_{8.15} = Π_{8.15}^{F}. Moreover, we have

(A_{2}, alarm) <_{CP1} (A_{3}, alarm) ≈_{CP2} (A_{2}, alarm):

There is only one minimal activation set for (A_{2}, alarm) that is a subset of �Π̂_{8.15}, namely {danger}. It is also a minimal immediate activation set for (A_{2}, alarm); to see this, take �:= {alarm} in Definition 8.7. There are only two minimal activation sets for (A_{3}, alarm) that are subsets of �Π̂_{8.15}, namely {danger} and {thirst}, but only the first one is an immediate activation set for (A_{3}, alarm). Note that (A_{2}, alarm) is strictly more specific than (A_{3}, alarm) in the sense of (A_{2}, alarm) ≵_{CP1} (A_{3}, alarm) by the inessential^{46} application of the rule danger←thirst of A_{3}, which is not admitted for immediate activation sets.

44See the discussion at the end of Example 8.15.

45It might also be interesting to see that the slight modification (via “weakly”), which we need here, occurred already in our first intuitive sketch of a notion of specificity in § 4.3 — long before the development of the CP2 notion, cf. [Wirth & Stolzenburg, 2013, § 3.2].

46This means inessential in the sense of Definition 8.6.

Furthermore, we have

(A_{1}, drink) <_{CP1} (A_{3}, alarm) △_{CP2} (A_{1}, drink):

The minimal [immediate] activation set {danger} for (A_{3}, alarm) is not an activation set for (A_{1}, drink). The only [immediate] activation set for (A_{1}, drink) that is a subset of �Π̂_{8.15} is {thirst}, which is an activation set for (A_{3}, alarm), but not a weakly immediate one. Note that (A_{1}, drink) is no longer more or equivalently specific than (A_{3}, alarm) in the sense of (A_{1}, drink) ≴_{CP2} (A_{3}, alarm), because the inessential application of the rule danger←thirst of A_{3} is not admitted for immediate activation sets.

In spite of these minor but noticeable differences, however, nothing has actually changed by stepping from CP1 to CP2, except the positioning of the argument (A_{3}, alarm), which is non-minimal as an argument (and therefore practically irrelevant and not even considered in many frameworks, cf. Remark 2.9 of § 2.4) and also non-minimal in ≲_{CP1} (and therefore less specific and not really relevant either). What is crucial, however, is that a most specific argument cannot be found in either case. Indeed, we have both

(A_{1}, drink) △_{CP1} (A_{2}, alarm)
and (A_{1}, drink) △_{CP2} (A_{2}, alarm).

If we remove danger from Π_{8.15}^{F}, then (A_{2}, alarm) is no argument anymore, but we can embed the specification injectively into the one of Example 3.3 of § 3 and get both

(A_{1}, drink) ≈_{CP1} (A_{3}, alarm)
and (A_{1}, drink) ≈_{CP2} (A_{3}, alarm),

because the activation set {thirst} now becomes an immediate one also for (A_{3}, alarm). Indeed, the application of the rule danger←thirst is no longer inessential for deriving alarm.

Moreover, if we now add the rule danger⇐thirst to Π_{8.15}^{G}, resulting in the specification ({thirst}, {danger⇐thirst}, Δ_{8.15}), then the situation is essentially the same as in Example 3.2 of § 3, and so we get both (A_{1}, drink) <_{CP1} (A_{3}, alarm) ≈_{CP1} (A_{2}, alarm) and (A_{1}, drink) <_{CP2} (A_{3}, alarm) ≈_{CP2} (A_{2}, alarm),

because — although the application of the rule danger←thirst becomes inessential again by danger ∈ �Π̂ — {thirst} now becomes a weakly immediate activation set for (A_{3}, alarm) and for (A_{2}, alarm), though not a (non-weakly) immediate one.

Corollary 8.16 (≲_{CP1} and ≲_{CP2} are incomparable) There are a specification (Π_{8.15}^{F}, Π_{8.15}^{G}, Δ_{8.15}) (without any negative literals) and arguments (A_{1}, L_{1}), (A_{3}, L_{3}), (A_{2}, L_{2}), such that (A_{1}, L_{1}) ≲_{CP1} (A_{3}, L_{3}) ≲_{CP2} (A_{2}, L_{2}) and (A_{1}, L_{1}) ≴_{CP2} (A_{3}, L_{3}) ≴_{CP1} (A_{2}, L_{2}),

i.e. ≲_{CP1} ⊈ ≲_{CP2} ⊈ ≲_{CP1}.

Nevertheless, Example 8.15 suggests that only some unimportant details make ≲_{CP1} and ≲_{CP2} incomparable to each other, but that the most specific minimal arguments seem to remain most specific and so nothing essential seems to change.

So we may ask ourselves: What changes occur in our previous examples when we switch from CP1 to CP2 ? Do any of the relations stated for CP1 change for CP2 ?

The answer to the latter question is: No! We would like to ask the reader to check this carefully.

Example 8.17 (continuing Example 7.7) Indeed, the only noticeable change at all occurs in Example 7.7, where {q(a)} is a minimal activation set for (A_{1}, ¬p(a)), but not an immediate activation set. Nevertheless, because {q(a)} is a weakly immediate activation set for (A_{1}, ¬p(a)), and because the only immediate activation set for (A_{1}, ¬p(a)) is {q(a), s(a)} (which is a weakly immediate activation set for (A_{2}, p(a)), though not {q(a)}, the only (non-weakly) immediate one), we have (A_{1}, ¬p(a)) ≈_{CP2} (A_{2}, p(a)), just as we have (A_{1}, ¬p(a)) ≈_{CP1} (A_{2}, p(a)).

Example 8.18 (continuing Example 8.1 of § 8.2.2) (Minimal argument with two minimal immediate activation sets) It is obvious that a minimal argument can easily have two minimal activation sets that are incomparable w.r.t. ⊆. For instance, already in Example 3.2 of § 3, the minimal argument (A_{2}, flies(edna)) has two minimal [simplified] activation sets, namely {bird(edna)} and {emu(edna)}, from which, however, only {bird(edna)} is an immediate activation set. Indeed, minimal arguments can have more than one minimal immediate activation set only if conditions of general rules directly contribute to the leaves of the isolated defeasible part as described in § 4.4.1.^{47} This is happens in Example 8.1 of § 8.2.2 for the minimal argument (A_{2}, h) : The general rule f⇐c∧e contributes the leaf c to the isolated defeasible part with root h, the inner nodes f and e, and the set of leaves {b, c}, which is one minimal immediate activation set of (A_{2}, h). Moreover, the general rule f⇐d∧e contributes the leaf d to the isolated defeasible part with root h, the inner nodes f and e, and the set of leaves {b, d}, which is the other minimal immediate activation set of (A_{2}, h), and also the only one for (A_{1}, ¬h). Thus, we get both (A_{1}, ¬h) <_{CP1} (A_{2}, h) and (A_{1}, ¬h) <_{CP2} (A_{2}, h).

8.3.2 Special Cases with Simple Activation-Set Computation

A typical problem in practical application is to classify rules automatically as being facts, general rules, or defeasible rules. We briefly discuss the trivial forms of such a classification now.

The first trivial form of classification is to take all proper rules as defeasible rules. Note that the following lemma (motivated by Example 8.18 of § 8.3.1) reduces the task of computing activation sets to the simpler task of computing minimal arguments.

Theorem 8.19 Assume that all rules in Π^{G} are just literals (i.e. have empty conditions). Let (A, L) be a minimal argument. Let � be the set of all condition literals of all rules in A. Then (A, L) has a unique minimal activation set H; and this H is actually a minimal immediate activation set for (A, L) and equal to � ∩ Π̂^{F} \ Π̂^{G}.

47Technically, it is possible to enforce a unique immediate activation set for each minimal argument by including the instances also of the general rules of the isolated defeasible part into the first element of the arguments. Intuitively, however, this is not reasonable because it leads to unintendedly incomparable arguments.

Proof of Theorem 8.19 Let (A, L) be a minimal argument. In case of L ∈ �Π̂, there is exactly one minimal activation set for (A, L), namely the empty set ∅, and this an immediate activation set (choose � := ∅ in Definition 8.7). Moreover, because (A, L) is a minimal argument, we have A = ∅, and then � = ∅. So we get our unique minimal activation set ∅ indeed in the claimed form of � ∩ Π̂^{F} \ Π̂^{G} = ∅ ∩ Π̂^{F} \ Π̂^{G} = ∅. It now remains to consider the case of L ∉ �Π̂. Because (A, L) is an argument, there is an and-tree for the derivation of Π̂^{F} ∪ A ∪ Π̂^{G} ⊢ {L}. As every and-tree is finite, there is a finite activation set H′ ⊆ Π̂^{F} for (A, L). Then there must be a minimal activation set H for (A, L) with H ⊆ H′. Then we have H ⊆ Π̂^{F}\Π̂^{G}. Then there is an and-tree T for the derivation of H ∪ A ∪ Π̂^{G} ⊢ {L} (which is actually unique, but this does not matter here). Let � be the set of all conclusions of all rules in A. Let �′ be the set of all literals in A (i.e. rules with empty conditions). Then �′ ⊆ � . Because (A, L) is a minimal argument, we know that � ∩ �Π̂ = ∅ and that every rule from A is applied in T. Thus, because of L ∉ �Π̂ and because all rules in Π̂ are just literals, the set of the labels of the leaves of T is exactly (� ∩ �Π̂) ∪ �′. Because T is an and-tree for the derivation of H ∪ A ∪ Π̂^{G} ⊢ {L}, because A ∩ �Π̂ ⊆ �′ ∩ �Π̂ ⊆ � ∩ �Π̂ = ∅, and because all rules in Π̂^{G} are just literals, we have

(a) � ∩ �Π̂ ⊆ (H ∪ A ∪ Π̂^{G}) ∩ �Π̂ = H ∪ ∅ ∪ Π̂^{G} = H ∪ Π̂^{G},

(b) �Π̂^{G} = Π̂^{G}, and (c) �Π̂ = Π̂^{F} ∪ Π̂^{G}. Because H is a minimal activation set for (A, L), H must be a subset of the leaves of T not in �′: H ⊆ � ∩ �Π̂. Because of our previous result of H ⊆ Π̂^{F}\Π̂^{G}, we now get H ⊆ � ∩�Π̂ ∩Π̂^{F}\Π̂^{G} ⊆_{(a)} (H ∪ Π̂^{G})∩Π̂^{F}\Π̂^{G} = H ∪∅ = H, i.e. H = � ∩�Π̂ ∩Π̂^{F}\Π̂^{G} =_{(c)} � ∩ (Π̂^{F} ∪ Π̂^{G}) ∩ Π̂^{F}\Π̂^{G} = � ∩ Π̂^{F}\Π̂^{G}. Choosing �:= {L} in item 1 of Definition 8.7, and a proof tree consisting only of a root in item 2, we see that H is actually an immediate activation set for (A, L); in particular we have L ∉ �Π̂ and the property required in the last line of item 1 of Definition 8.7: (� ∩ �Π̂) ∪ �′ ⊆_{(a)} H ∪ Π̂^{G} ∪ A =_{(b)} H ∪ �Π̂^{G} ∪ A. Finally, H is a minimal immediate activation set by Corollary 8.8(5). Q.e.d. (Theorem 8.19)

The second trivial form of classification is to take all rules without conditions to be defeasible. It is not a good idea for comparing arguments w.r.t. specificity, however:

Corollary 8.20 Assume that Π^{F} = ∅ and that Π^{G} contains only rules with non-empty conditions. Then we have �Π̂ = ∅. Moreover, for every argument, there is exactly one [immediate] activation set H with H ⊆ �Π̂, namely H = ∅. Furthermore, all arguments are equivalent w.r.t. ≈_{CP1} and ≈_{CP2}.

Finally, note that the computation of simplified activation sets that are a subset of �_{Π̂∪Δ̂} — as required for P1, P2, P3 instead of CP1, CP2 — is not simplified for the special cases of this section, contrary to the computation of [immediate] activation sets that are subsets of �Π̂.

8.3.3 A Step Toward Operationalization of Immediate Activation Sets

Let us assume that the sets of our predicate and function symbols are enumerable and contain only symbols with finite arities. This assumption does not seem to restrict practical application.

It is straightforward to enumerate for a given input literal — say in a top-down SLDresolution style — the and-trees of all possible derivations of instances of this input literal, and to interleave this enumeration of and-trees with the enumeration of all ground instances of each and-tree, and finally to enumerate for each ground instance of an and-tree all activation sets for all contained arguments and the ground instance of the input literal labeling the root. Indeed, this is possible because �Π̂ is enumerable (i.e. semi-decidable) by our above assumption.

To do the same for all immediate activation sets, we have to require the co-semi-decid-ability of �Π̂, because, in general, we cannot output an activation set supposed to be an immediate one before we have established that the literals labeling the ancestors of the nodes of its literals really do not occur in �Π̂.

So let us assume the decidability of �Π̂ for the remainder of this section.^{48}

It is much harder, however, to enumerate all activation sets in an SLD-like derivation style directly, i.e. without storing the intermediate and-trees and their instances. Although immediate activation sets offer a crucial advantage for a direct enumeration in principle (because they admit to cut off inessential^{49} derivations of literals), the imperative, tailrecursive procedure we will sketch in this section (cf. Figure 2) still needs further refinement. This procedure enumerates the immediate activation sets directly, unless it sometimes outputs the character string "breach", which indicates that some immediate activation sets may be missing.

We present the procedure of Figure 2 here mainly because we want to concretize the tasks that still remain to be solved for obtaining a Poole-style notion of specificity that admits a sufficiently efficient operationalization, and because our solution of these tasks in § 8.3.4 may not be the only way to solve them.

Let us assume that picking elements from sets satisfies some fairness restriction in the sense that every element will be picked eventually. Moreover, let us assume that we have a procedure to decide �Π̂. Furthermore, let us assume that L is a literal with L ∉ �Π̂.

Under these assumptions, the SLD-like procedure immediate-activation-sets(L) of Figure 2 has the following two properties:

1. If it outputs (H, (A, I)) then I ∉ �Π̂ is an instance of L, we have A ≠ ∅, and H ⊆ �Π̂ is an immediate activation set for the argument (A, I).

2. If it never outputs "breach", then, for each instance Lϱ ∉ �Π̂ with a minimal immediate activation set H′ for an argument (A, Lϱ), it outputs some (H, (A, I)) such that there is a substitution μ with (Aμ, Iμ) = (A, Lϱ) and H′ = Hμ \ (�Π̂^{G} ∪ Aμ). As this is similar to what is called a “most general unifier”, we may speak of all maximally general, immediate activation sets with arguments here. procedure immediate-activation-sets(L): (* L must be a literal *)

48We will relax this restriction in § 8.3.4.

49This means inessential in the sense of Definition 8.6.

if L ∉ �Π̂ then (call immediate-activation-sets-helper({(L, 2)}, ∅, ∅, ∅, L)).

procedure immediate-activation-sets-helper(T, O, H, A, I): (* T is the current goal. T must be a set of pairs (L, B) of a literal L ∉ �Π̂ and

a bit B ∈ {1, 2} referring to the two items of Definition 8.7, such that B = 1 indicates that L labels a defeasible part *)

(* O is a set of literals that indicate that our algorithm may have missed to enumerate a most general immediate activation set in case of O ∩ �Π̂ ≠ ∅ because the and-tree has already been properly expanded at their nodes (which occur in a defeasible part!) *)

(* H is an accumulator for the immediate activation set,

H must always be a set of literals L ∈ �Π̂ from the fringes of defeasible parts *) (* A is an accumulator for the first element of the argument *) (* I is the possibly instantiated input literal and second element of the argument *)

if T = ∅ then (output "H is immediate activation set for (A, I)" and exit); pick some (L, B) from T; T := T \ {(L, B)}; for each rule (L′⇐L′′_{1}∧ … ∧L′′_{n}) ∈ Π ∪ Δ do for some ξ that maps all variables in L′⇐L′′_{1}∧ … ∧L′′_{n} to fresh variables do if L and L′ξ have the most general unifier σ then [

I′ := Iσ; if I′ ∈ �Π̂ then (output "Instance I′ ∈ �Π̂" and exit); O′ := Oσ; if O′ ∩ �Π̂ ≠ ∅ then (output "breach" and exit); T′ := { (L′′′σ, B′′′) | (L′′′, B′′′) ∈ T ∧ L′′′σ ∉ �Π̂ }; H′ := Hσ ∪ { L′′′σ | (L′′′, 1) ∈ T ∧ L′′′σ ∈ �Π̂ }; A′ := Aσ; if Lσ ∈ �Π̂ then (if B = 1 then (H′ := H′ ∪ {Lσ})) else (

B′ := B;
if (L′⇐L′′_{1}∧ … ∧L′′_{n}) ∉ Π then (

(* The applied rule is necessarily a defeasible one! *)

A′ := A′ ∪ {(L′⇐L′′_{1}∧ … ∧L′′_{n})ξσ};

B′ := 1);

T′ := T′ ∪ { (L′′_{i}ξσ, B′) | i ∈ {1, …, n} ∧ L′′_{i}ξσ ∉ �Π̂ };
if B′ = 1 ∧ n≥1 then (

(* B′ = 1 means that we are in a defeasible part now,

and so we have to accumulate our activation set! *) (* n≥1 means that we have to expand the and-tree properly

under the crucial assumption that Lσ ∉ �Π̂. *) H′ := H′ ∪ { L′′_{i}ξσ | i ∈ {1, …, n} ∧ L′′_{i}ξσ ∈ �Π̂ };

O′ := O′ ∪ {Lσ}));

O′ := { L′′′ ∈ O′ | L′′′ is not ground };

call immediate-activation-sets-helper(T′, O′, H′, A′, I′)].

Figure 2: Sketch of immediate-activation-sets and immediate-activation-sets-helper Remark 8.21 (Restriction to Ground Conclusions Prevents "breach") In the special case that the conclusions of all rules of Π^{G} ∪ Δ with non-empty condition are ground, however, the call of the procedure immediate-activation-sets(L) is guaranteed not to output "breach", simply because then only ground literals can enter the set of the program variable O′, which are immediately removed again by the line before the tail-recursive call.

Remark 8.22 (Restriction to Ground Input Literals Does Not Prevent "breach") Note that a restriction to input literals that are ground does not really solve the crucial problem (of which the program variables O, O′ have to take care in Figure 2) that a literal with free variables may be not in �Π̂, whereas some of its instances actually are in �Π̂. The main source of the free variables here are the extra-variables, i.e. the free variables that occur in the condition but not in the conclusion of a rule. Such rules with extra-variables and non-ground conclusions, however, are standard in positive-conditional specification, just as in logic programming. A single extra-variable in an arbitrary rule of Π^{G} ∪ Δ can force SLD-resolution to work on non-ground goals even for a ground input literal.

Some examples may be more appropriate here than a proof of the soundness of the procedure of Figure 2 (that enumerates a maximally general, immediate activation set for each minimal immediate activation set unless it sometimes indicates "breach"), because we see the procedure only as a step in a further development toward a tractability that is sufficient in practice. Therefore, we will give some examples here on how the procedure

immediate-activation-sets(L)

works for certain literals L ∉ �Π̂, namely by

listing all calls of the auxiliary procedure immediate-activation-sets-helper.

Example 8.23 (continuing Example 7.7 of § 7.4) Let us start with Example 7.7 of § 7.4, which we recently reconsidered in Example 8.17. A call of immediate-activation-sets(¬p(a)) results in a call of immediate-activation-sets-helper with the argument quintuple ( {(¬p(a), 2)}, ∅, ∅, ∅, ¬p(a) ), where the only rule whose conclusion is unifiable with the only goal literal is a defeasible one, namely ¬p(x)←q(x)∧s(x) from Δ_{7.7}. We can take ξ and σ as the identity and {x↦a}, respectively. The program variable B′ will be set to 1, and the tail-recursive call will have the argument tuple

( ∅, ∅, {q(a), s(a)}, {¬p(a)←q(a)∧s(a)}, ¬p(a) ).

This call immediately terminates by outputting the immediate activation set {q(a), s(a)} for the argument ( {¬p(a)←q(a)∧s(a)}, ¬p(a) ). As all calls are terminated now and there was no output of "breach", this means that we have enumerated all immediate activation sets for the input literal.

Example 8.24 (continuing Example 3.3 of § 3) Let us now come to Example 3.3 of § 3. A call of immediate-activation-sets(flies(y)) results in a call of immediate-activation-sets-helper with the argument quintuple

( {(flies(y), 2)}, ∅, ∅, ∅, flies(y) ),

where the only rule whose conclusion is unifiable with the only goal literal is a defeasible one, namely flies(x)←bird(x) from Δ_{3.3}. We can take ξ and σ as the identity and {x↦y}, respectively. The program variable B′ will be set to 1, and the tail-recursive call will have the argument tuple

( {(bird(y), 1)}, {flies(y)}, ∅, {flies(y)←bird(y)}, flies(y) ).

Again the only rule whose conclusion is unifiable with the only goal literal is a defeasible one, namely bird(x)←emu(x) from Δ_{3.3}. We can again take ξ and σ as the identity and {x↦y}, respectively. The program variable B′ will be set to 1, and the tail-recursive call will have the argument tuple

( {(emu(y), 1)}, {flies(y), bird(y)}, ∅, {flies(y)←bird(y), bird(y)←emu(y)}, flies(y) ). Now the only rule whose conclusion is unifiable with the only goal literal is a fact, namely emu(edna) from Π_{3.3}^{F}. We can take ξ and σ as the identity and {y↦edna}, respectively. The program variable B′ will be set to 1, and the tail-recursive call will have the argument tuple ( ∅, ∅, {emu(edna)}, {flies(edna)←bird(edna), bird(edna)←emu(edna)}, flies(edna) ). This call immediately terminates by outputting the immediate activation set {emu(edna)} for the argument ( {flies(edna)←bird(edna), bird(edna)←emu(edna)}, flies(edna) ). As all calls are terminated now and there was no output "breach", this means that we have enumerated all immediate activation sets for all instances of the input literal.

Example 8.25 (continuing Example 3.2 of § 3) Let us now come to Example 3.2 of § 3. We start with the same input as for Example 8.24 above, and there is no change up to the call with argument tuple

( {(bird(y), 1)}, {flies(y)}, ∅, {flies(y)←bird(y)}, flies(y) ),

and the only difference before the next call is that the applied rule is a strict one and is not recorded in the program variable A′. Thus, we get a call with the argument tuple

( {(emu(y), 1)}, {flies(y), bird(y)}, ∅, {flies(y)←bird(y)}, flies(y) ).

There is still no essential change, except that the test for "breach" becomes positive: We again have Oσ = {flies(edna), bird(edna)}, but now we have bird(edna) ∈ �Π̂, and our procedure outputs "breach". Indeed, it missed to enumerate the immediate activation set {bird(edna)} for the argument ({flies(edna)←bird(edna)}, flies(edna)), simply because the instantiation came too late to stop us from proper expansion of the and-tree.

Remark 8.26 (Closer Matching of Activation Sets to SLD-Resolution

Results in Inappropriate Semantics)

The obvious idea to avoid the possibility that the procedure of Figure 2 may output "breach" and miss some maximally general, immediate activation sets is the following.

Just like we obtained CP2 from CP1, it is possible to obtain a notion CP3 from CP2 by a minor modification of immediate activation sets, resulting in, say, SLD activation sets, such that the SLD-like computation of Figure 2 enumerates all maximally general, SLD activation sets.

We do not see a chance to satisfy the crucial requirement of such a modification, however, namely that it does not affect any of our previous examples. If we look at the application of the procedure of Figure 2 to the specification of Example 3.2 as described in Example 8.25, then we see that all SLD activation sets remaining in Example 3.2 could be {emu(edna)}, such that the arguments (A_{1}, ¬flies(edna)) and (A_{2}, flies(edna)) would become equivalently specific w.r.t. the specification of Example 3.2, which seems to be absurd.

8.3.4 A Specificity Relation Based on Given And-Trees

We see no straightforward procedure to decide ≲_{CP2}. Even worse, we see neither a procedure to semi-decide it, nor a procedure to co-semi-decide it. A positive answer can be given if the procedure of Figure 2 terminates for the first argument of ≲_{CP2} without outputting "breach". A negative answer can be given if, for an immediate activation set enumerated for the first argument, the derivation for testing the property of being a weakly immediate activation set for the second argument terminates with failure. In general, even if we assume �Π̂ to be decidable, none of these terminations is guaranteed.^{50}

In such a situation it is clearly appropriate to relax our requirement of a model-theoretic specificity relation a bit. So we replace the fancied decision procedure for �Π̂ with the test whether the literal has a derivation from those instances of Π which can be found in some and-tree occurring in a finite set of and-trees fixed in advance. For the solution we are aiming at, it is crucial that this given finite set of and-trees cannot be further extended during related specificity considerations. A good candidate may be the set of those and-trees that our derivation procedure has been able to construct within a certain time limit.

Then we can replace each of the three elements of our specification (Π^{F}, Π^{G}, Δ) with the sets of those instances of their elements that are actually applied in our finite set of and-trees, resulting in the new specification (Π_{g}^{F}, Π_{g}^{G}, Δ_{g}). The further considerations must use these three finite sets without any further instantiation. This means that their rules are to be considered to be ground and this is what the lower index “g” stands for.

We again abbreviate Π_{g} := Π_{g}^{F} ∪ Π_{g}^{G}, and also replace the typically undecidable set �Π̂ with finite set �_{Π_{g}}.

Note that hardly anything has changed for our set of defeasible rules, because arguments work anyway with instances that are ground, or are at least treated as if they were ground (cf. Remark 2.8 in § 2.4), and we can hardly consider an argument that is not contained in some and-tree we have constructed in advance.

There is a major change, however, for the set Π of strict rules. The situation here is similar to an expansion w.r.t. a champ fini in Herbrand’s Fundamental Theorem,^{51} and we have reason to hope that the effect of this change can be neglected in practice, provided that a sufficient number of the proper instances is considered. Note that, for firstorder logic, the depth limit n for terms required for Herbrand’s Property C to establish a sentential tautology (i.e. the natural number n for the champ fini of order n) is not computable in the sense of a total recursive function. Even if we knew the smallest such n, however, the number of terms of depth smaller than n would still be too high for practical feasibility in general. This means that it is crucial to choose the instances of our rules in a clever way, say from the successful proofs delivered by a theorem-proving system within a sufficient time limit.

50Both of these terminations can be guaranteed, however, under most restrictive conditions, such as the one that the conclusions of every defeasible rule from Π^{G} ∪ Δ with a non-empty condition are ground (cf. Remark 8.21).

51Cf. [Herbrand, 1930], [Wirth &al., 2009; 2014], [Wirth, 2012; 2014].

Remark 8.27 (Specificity Relation on Arguments Extended with an And-Tree) A straightforward idea to improve tractability is to attach an and-tree to each argument and to compute a unique^{52} immediate activation set for each argument as follows:

Starting from the root, we traverse the tree, remembering whether we have passed an application of the instance of a defeasible rule, and stop traversing at the first node labeled with an element of the finite set �_{Π_{g}}, outputting its literal as part of the single tree-immediate activation set, provided that we have passed an application of the instance of a defeasible rule.

The problem we see here, however, is that such a fixed and-tree does not make much sense for the second argument of our relation ≲_{CP2}, simply because we should not let an inappropriately chosen and-tree for the second argument produce a failure of the property of being more specific, cf. Example 8.1 of § 8.2.2. This means that we need an existential quantification over the and-tree of the second argument. If we were able to find a way to handle this quantification, the same technique would probably admit us to handle a universal quantification over the and-tree of the first argument, which brings us back to our original relation ≲_{CP2} on arguments without and-trees.

So this restriction to concrete and-trees does not seem to help. We will now show that we do not need it either.

procedure ground-immediate-activation-sets-helper(T, H, A): (* T is the current goal. T must be a set of pairs (L, B) of a literal L ∉ �_{Π_{g}} and

a bit B ∈ {1, 2} referring to the two items of Definition 8.7, such that B = 1 indicates that L labels a defeasible part *)

(* H is an accumulator for the immediate activation set. H must always be

a set of literals L ∈ �_{Π_{g}}\�_{Π_{g}^{G}} from the fringes of defeasible parts. *) (* A is an accumulator for the first element of the argument with A∩�_{Π_{g}} = ∅. *) (* note that the input literal I is invariant now; no input, no output *)

if T = ∅ then (output (H, A) and exit);

pick some (L, B) from T; T := T \ {(L, B)};

(* We do not have to test rules from Π_{g}^{F} because of L ∉ �_{Π_{g}}. *)

for each rule (L′⇐L′′_{1}∧ … ∧L′′_{n}) ∈ Π_{g}^{G} ∪ Δ_{g} do

if L = L′ then [ H′ := H; A′ := A; B′ := B;

if (L′⇐L′′_{1}∧ … ∧L′′_{n}) ∉ Π_{g}^{G} then (

(* The applied rule is now necessarily a defeasible one. *)

A′ := A′ ∪ {(L′⇐L′′_{1}∧ … ∧L′′_{n})};

B′ := 1);

T′ := T ∪ { (L′′_{i}, B′) | i ∈ {1, …, n} ∧ L′′_{i} ∉ �_{Π_{g}} };
if B′ = 1 then (

(* B′ = 1 means that we are in a defeasible part now,

and so we have to accumulate our activation set! *) H′ := H′ ∪ { L′′_{i} | i ∈ {1, …, n} ∧ L′′_{i} ∈ �_{Π_{g}}\�_{Π_{g}^{G}} });

call ground-immediate-activation-sets-helper(T′, H′, A′)].

Figure 3: Sketch of procedure ground-immediate-activation-sets-helper

52See, however, Example 8.18 in § 8.3.1.

With the modifications described above, let us now come back to our procedure of Figure 2. As noted before (cf. Remark 8.21), there cannot be any output of "breach" anymore, because our new sets of general strict and defeasible rules, i.e. the sets Π_{g}^{G} and Δ_{g}, are now ground by definition. After the resulting simplifications, the procedure immediate-activation-sets-helper now may be replaced with the procedure ground-immediate-activation-sets-helper sketched in Figure 3.

To ensure termination of ground-immediate-activation-sets-helper we additionally have to store the current path of the and-tree and exit without further output if we encounter a literal for a second time on the same path.

Remark 8.28 (Considerations on Complexity) Regarding time complexity of the procedure of Figure 3 extended with the storage of the current path of the and-tree for ensuring termination mentioned above, only the following preliminary remarks apply in this early state of development.

From practical experience, complexity is not relevant yet: Our straightforward Prolog (cf. e.g. [Clocksin & Mellish, 2003]) implementation of this procedure (which prefers simplicity of coding over efficiency) computes, compares, and sorts — without any noticeable delay in the answer — all minimal immediate activation sets for all minimal arguments for all literals of �_{Π_{g}∪Δ_{g}}\�_{Π_{g}}, for a specification (Π_{g}^{F}, Π_{g}^{G}, Δ_{g}) of all instances required for a superset of all examples in this paper.

Regarding the theoretical worst case, which will hardly ever occur in practice, the following first estimate may be not completely irrelevant. Let n be the number of different literals in all conclusions of all rules of Π_{g} ∪ Δ_{g}. With our mentioned mechanism for ensuring termination, it is obvious that n limits the maximal depth of the SLD-like search tree. Let m be the maximal number of all condition literals of all rules with an identical conclusion. It is obvious that m limits the maximal number of children of any node in the SLD-like search tree, cumulated over the whole run. This means that the maximal size of the cumulated search tree is m^{n−1}−1, i.e. O(m^{n}). Luckily, this Landau-O limits also the size of the theory �_{Π_{g}} (which we pre-compute in our Prolog implementation) and all other efforts at each node, such as indexing our rules for obtaining a constant effort at each node. Therefore, the whole algorithm is O(m^{n}).

Now we can compute the finite set of all minimal^{53} immediate activation sets of all minimal arguments for a given input literal w.r.t. our ground specification (Π_{g}^{F}, Π_{g}^{G}, Δ_{g}). All what is left for deciding ≲_{CP2} is to check whether each of the computed immediate activation sets whose defeasible rules are part of the first argument is a weakly immediate activation set for the second argument. This is straightforward, although it is not clear yet which implementation will be optimal.

We should not forget, however, that the specification (Π_{g}^{F}, Π_{g}^{G}, Δ_{g}) is only a reasonably constructed sub-specification of our original specification (Π^{F}, Π^{G}, Δ), which actually stands for (Π̂^{F}, Π̂^{G}, Δ̂). Practical tests have to show whether such an omission of infinitely many instances can be viable without deteriorating our specificity ordering. Theoretically, such a viability can only be guaranteed for the special case that the number of instances of the rules of the specification is finite (up to renaming of variables).

9 Conclusion

9.1 Summary

We would need further discussions on our surprising new findings w.r.t. Poole’s specificity relation, in particular its lack of transitivity. After all, defeasible reasoning with Poole’s notion of specificity is being applied now for over a quarter of century, and it was not to be expected that our investigations could shake an element of the field to the very foundations.

One remedy for the discovered lack of transitivity of ≲_{P3} could be to consider the transitive closure of the non-transitive relation ≲_{P3}. This could be an advantage compared to ≲_{CP1} only under the condition that the transitive closure of ≲_{P3} is a subset of ≲_{CP1}, i.e. only under one of the conditions of Theorem 6.16. Moreover, this transitive closure will still have the intuitive shortcomings made obvious in § 7. Furthermore, we do not see how this transitive closure could be decided efficiently. Finally, the transitive closure lacks a direct intuitive motivation, and after the first extension step from ≲_{P3} to its transitive closure, we had better take the second extension step to the more intuitive ≲_{CP1} immediately.

Contrary to the transitive closure of ≲_{P3}, our novel relations ≲_{CP1} and ≲_{CP2} also solve the problem of non-monotonicity of specificity w.r.t. conjunction (cf. § 7.1), which was already realized as a problem of ≲_{P1} by Poole [1985] (cf. Example 7.1).

The present means to decide our novel specificity relation ≲_{CP1}, however, show several improvements^{54} and a few setbacks^{55} compared to the known ones for Poole’s relation. Further work is needed to improve efficiency.

By a minor restriction of activations sets, resulting in immediate activations sets, we have come in § 8.3 to the quasi-ordering ≲_{CP2}, which does not show any difference compared to ≲_{CP1} in any of our examples except Example 8.15, which was constructed to show the difference. The new specificity ordering ≲_{CP2} has advantages w.r.t. intuition and efficiency. The latter advantage, however, requires decidability of �Π̂ (in addition to the always given semi-decidability). To concretize the problems of computing activation sets by SLD-resolution, we have sketched a procedure that may indicate "breach" if it may have missed some output in § 8.3.3. Then, in § 8.3.4, we have shown how to obtain decidability of �Π̂ by restriction to a finite set of instances that are then treated as if they were ground. Without such a restriction we do not know how to decide any of the relations ≲_{P1}, ≲_{P2}, ≲_{P3}, ≲_{CP1}, ≲_{CP2} in general; and we hope that we can find a procedure for generating the finite set of rule instances such that the effect of this restriction can be neglected in practice.

53Minimal immediate activation sets are obtained after completion of the procedure of Figure 3 simply as follows: For each minimal argument (A, L), we remove all proper supersets among the immediate activation sets. Note that we do not have to filter the immediate activation sets by removing all elements of A, simply because, as subsets of �_{Π_{g}}, they are disjoint from the literals in A (i.e. the rules with empty conditions).

54See §§ 8.1, 8.2.1, 8.3.2, 8.3.3, and 8.3.4 for the improvements.

55See §§ 8.2.3 and 8.3.3 for the setbacks.

9.2 Application Context

We plan to apply the specificity relations to question answering in the context of the RatioLog project, funded by the DFG (German Research Assoc.). Question answering systems such as LogAnswer [Furbach &al., 2010] usually determine several possible answer candidates for a given query. For each candidate, a possibly defeasible derivation of the answer is available. The best answer candidate has to be chosen. One idea among others is to prefer more specific answers. Thus, specificity is incorporated as a mechanism of rationality here.

An important part of the application context for specificity orderings consists of numerous frameworks for argumentation in logic. The overall process usually includes a dialectical process used for answering queries. Different arguments are pro or contra a certain answer. By means of an attack relation, conflicts between contradicting arguments can be determined in abstract argumentation frameworks, such as the ones of [Dung, 1995], [Prakken & Vreeswijk, 2002], and [Modgil & Prakken, 2014]. A concrete specificity or similar relation helps then to decide among conflicting arguments.

The ASPIC+ framework [Modgil & Prakken, 2014] combines an (abstract) argumentation system with a concrete knowledge base, which may contain strict and defeasible rules. In this context, an argument can be attacked on a conclusion of a defeasible inference, on a defeasible inference step itself, or on an ordinary premise. Nonetheless, also ASPIC+ is not a concrete system but a framework for specifying systems. The choice of the logic is left open in ASPIC+. Thus, on the basis of the different rule types, the attack or conflict relation may be defined, e.g. by means of one of our specificity relations.

As the discussion in this paper demonstrates, it is not that easy, however, to find an effective concrete specificity relation. One of the main problems is that such relations are often computationally highly complex (such as in [Kern-Isberner & Thimm, 2012]).

Moreover, we have to distinguish between orderings for comparing conflicting arguments w.r.t. specificity and orderings for comparing arguments w.r.t. a form of subsumption, such as the quasi-ordering of being “more conservative” found in [Besnard & Hunter, 2001, Definition 3.3, p. 206], [Besnard &al., 2013, Definition 6, p. 50]). There, roughly speaking, an argument (A_{1}, L_{1}) is more conservative than an argument (A_{2}, L_{2}) if A_{1} ⊆ A_{2} and {L_{2}} ⊢ {L_{1}}. So if our opponent accepts the argument (A_{2}, L_{2}), then he also has to accept our more conservative argument (A_{1}, L_{1}), because we need less presuppositions and our result follows from our opponent’s result. In many practical situations, however, the less conservative argument will be preferred. For instance, when we ask a question-answering system (such as LogAnswer [Furbach &al., 2010]) for the mother of Pierre Fermat, then — as an answer — we prefer^{56} the less conservative argument

(A, Mother(Claire de Long, Pierre Fermat)) to
(A, ∃x. Mother(x, Pierre Fermat)).

Moreover, the arguments (A, Mother(Françoise Cazeneuve, Pierre Fermat)) and (A, Mother(Claire de Long, Pierre Fermat)),

are incomparable in the “more conservative”-quasi-ordering. Even worse, for a non-trivial derivability relation, i.e. in a non-contradictory theory, this quasi-ordering cannot compare arguments with contradictory results L, ¬L by definition, and none of the arguments of our examples can be compared by this quasi-ordering.

9.3 Critical Assessment

It has become clear in several discussions that the main obstacle for an acceptance of one of our relations ≲_{CP1} or ≲_{CP2} as a replacement for ≲_{P3} is the change this brings to Example 3.3 of § 3: Some scientists working in the field have become used to the preference given by ≲_{P3} in this most popular example — so much that they now consider that preference a must. Note that the situation in Example 3.3 is actually most unstable under the two following aspects:

1. The preference chosen by ≲_{P3} in Example 3.3 has justifications that are intuitive and valid, but are in general uncorrelated to specificity, such as the preference of conservativeness or the non-model-theoretic preference of defeasible derivations of shorter length. In particular in this example, such intuitive justifications easily contaminate the readers’ intuition w.r.t. specificity. Moreover, as the arguments in Example 3.3 are not incomparable, but just equivalent according to ≲_{CP1}, we can easily combine ≲_{CP1} lexicographically with another ordering, say “minimum in the ordering of the natural numbers, for all and-trees, of the maximal length of defeasible paths”, and so recover the traditional preference of Example 3.3.

2. The situation of the example is chaotic in the sense that different preferences result from minor changes that may escape the readers’ disambiguation. For instance, if we add the general rule of the example that precedes Example 3.3 (i.e. of Example 3.2), then the preference chosen by ≲_{P3} is chosen by ≲_{CP1} and ≲_{CP2} as well. Moreover, if we alternatively add bird(edna) as a fact, then we can embed the example injectively into Example 8.15 of § 8.3.1, and then the preference chosen by ≲_{P3} is again chosen by ≲_{CP1}, whereas the arguments become incomparable w.r.t. ≲_{CP2}.

Already the examples in § 7 show, however, that ≲_{P3} almost always fails to prefer any argument in slightly bigger examples, not to speak of big ones. Indeed, ≲_{P3} can be considered a reasonable choice only if we restrict our considerations to tiny examples. Moreover, we presented good intuitive reasons for the failure of the preference of Example 3.3 in Example 6.20 of § 6.6 (cf. also the pointers to further reasons in Note 32).

It is just too early for a further assessment, and the further implications of the contributions of this paper and the technical details of the operationalization of our correction of Poole’s specificity will have to be discussed in future work.

56Let us compare our specificity relations P3, CP1, CP2 with the “more conservative”-quasi-ordering by looking at our Corollaries 6.7, 6.13, and 8.11 in the context of Corollary 6.8. So let us assume A_{1} ⊆ A_{2}.

For the trivial case of L_{1} = L_{2}, the argument (A_{1}, L_{1}) is quasi-smaller than the argument (A_{2}, L_{2}) for all of P3, CP1, CP2, and “more conservative”. In case of L_{2} ∈ �Π̂ ⇒ L_{1} ∈ �Π̂ and {L_{1}} ∪ Π̂ ⊢ {L_{2}}, again the argument (A_{1}, L_{1}) is quasi-smaller than the argument (A_{2}, L_{2}) for all of P3, CP1, CP2, but for “more conservative” it is the other way round, provided that we adopt the straightforward assumption that derivability is derivability w.r.t. the basic theory of Π̂. Thus, P3, CP1, CP2 would all prefer (A, Mother(Claire de Long, Pierre Fermat)) to (A, ∃x. Mother(x, Pierre Fermat)), provided that we could express existential quantification.

Acknowledgments

This research has been supported by the DFG (German Research Assoc.) grant Sto 421/5-1.

We would like to thank Matthias Thimm for his helpful discussions of Example 3.3. Moreover, we are deeply obliged to several anonymous reviewers of previous versions of this paper for their most profound critiques and suggestions for improvement, which have been an enormous help to improve the quality of presentation considerably.

To honor David Poole, let us end this paper with the last sentence of [Poole, 1985]: This research was sponsored by no defence department.

References

[Aiello &al., 1996] Luigia Carlucci Aiello, Jon Doyle, and Stuart C. Shapiro, editors. Proc. 5^{th} KR 1996 — Int. Conf. on Principles of Knowledge Representation and Reasoning, Nov. 5–8, 1996, Cambridge (MA). Morgan Kaufmann (Elsevier), Los Altos (CA), 1996.

[Baral &al., 2014] Chitta Baral, Giuseppe De Giacomo, and Thomas Eiter, editors. Proc. 14^{th} KR 2014 — Int. Conf. on Principles of Knowledge Representation and Reasoning, Jul 20–24, as part of the Vienna Summer of Logic, Vienna, July 9–24, 2014. AAAI Press, 2014. http:

//www.kr.org/index.php?page=proclist.

[Benferhat & Garcia, 1997] Salem Benferhat and Laurent Garcia. A coherence-based approach to default reasoning. 1997. In [Gabbay &al., 1997, pp. 43–57]. http://dx.doi.org/

10.1007/BFb0035611.

[Besnard & Hunter, 2001] Philippe Besnard and Anthony Hunter. A logic-based theory of deductive arguments. Artificial Intelligence, 128:203–235, 2001. Received Dec. 8, 2000. http:

//dx.doi.org/10.1016/S0004-3702(01)00071-6.

[Besnard &al., 2013] Philippe Besnard, Éric Grégoire, and Badran Raddaoui. A conditional logic-based argumentation framework. 2013. In [Liu &al., 2013, pp. 44–56]. http://dx.doi.

org/10.1007/978-3-642-40381-1_4.

[Chesñevar &al., 2003] Carlos I. Chesñevar, Jürgen Dix, Frieder Stolzenburg, and Guillermo R. Simari. Relating defeasible and normal logic programming through transformation properties. Theoretical Computer Sci., 290:499–529, 2003. Received Jan. 8, 2001; rev. Nov. 9, 2001. http:

//dx.doi.org/10.1016/S0304-3975(02)00033-6.

[Clocksin & Mellish, 2003] William F. Clocksin and Christopher S. Mellish. Programming in Prolog. Springer, 2003. 5^{th} edn. (1^{st} edn. 1981).

[Dung & Son, 1996] Phan Minh Dung and Tran Cao Son. An argumentation-theoretic approach to reasoning with specificity. 1996. In [Aiello &al., 1996, pp. 506–517].

[Dung, 1995] Phan Minh Dung. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artificial Intelligence, 77:321–

358, 1995. http://dx.doi.org/10.1016/0004-3702(94)00041-X.

[Furbach &al., 2010] Ulrich Furbach, Ingo Glöckner, and Björn Pelzer. An application of automated reasoning in natural-language question answering. AI Comm., 23:241–265, 2010.

[Gabbay & Woods, 2004ff.] Dov Gabbay and John Woods, editors. Handbook of the History of Logic. North-Holland (Elsevier), 2004ff..

[Gabbay &al., 1997] Dov Gabbay, Rudolf Kruse, Andreas Nonnengart, and Hans-Jürgen Ohlbach, editors. Proc. 1^{st} Int. Joint Conf. on Qualitative and Quantitative Practical Reasoning, 1997, June 9–12, Bad Honnef (Germany), number 1244 in Lecture Notes in Computer Science. Springer, 1997.

[Gabbay, 2002] Dov Gabbay, editor. Handbook of Philosophical Logic. Kluwer (Springer Science+Business Media), 2002. 2^{nd} edn..

[García & Simari, 2004] Alejandro J. García and Guillermo R. Simari. Defeasible logic programming: An argumentative approach. Theory and Practice of Logic Programming, Cambridge Univ. Press, 4:95–138, 2004.

[Gelfond & Przymusinska, 1990] Michael Gelfond and Halina Przymusinska. Formalization of inheritance reasoning in autoepistemic logic. Fundamenta Informaticae, XIII:403–443, 1990.

[Gillman, 1987] Leonard Gillman. Writing Mathematics Well. The Mathematical Association of America, 1987.

[Goldfarb, 1970] Warren Goldfarb. Review of [Herbrand, 1968]. The Philosophical Review, 79:576–578, 1970.

[Heijenoort, 1971] Jean van Heijenoort. From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931. Harvard Univ. Press, 1971. 2^{nd} rev. edn. (1^{st} edn. 1967).

[Herbrand, 1930] Jacques Herbrand. Recherches sur la théorie de la démonstration. PhD thesis, Université de Paris, 1930. Thèses présentées à la faculté des Sciences de Paris pour obtenir le grade de docteurès sciences mathématiques — 1^{re} thèse: Recherches sur la théorie de la démonstration — 2^{me} thèse: Propositions données par la faculté, Les équations de Fredholm — Soutenues le 1930 devant la commission d’examen — Président: M. Vessiot, Examinateurs: MM. Denjoy, Frechet — Vu et approuvé, Paris, le 20 Juin 1929, Le doyen de la faculté des Sciences, C. Maurain — Vu et permis d’imprimer, Paris, le 20 Juin 1929, Le recteur de l’Academie de Paris, S. Charlety — No. d’ordre 2121, Série A, No. de Série 1252 — Imprimerie J. Dziewulski, Varsovie — Univ. de Paris. Also in Prace Towarzystwa Naukowego Warszawskiego, Wydział III Nauk Matematyczno-Fizychnych, Nr. 33, Warszawa. A contorted, newly typeset reprint is [Herbrand, 1968, pp. 35–153]. Annotated English translation Investigations in Proof Theory by Warren Goldfarb (Chapters 1–4) and Burton Dreben and Jean van Heijenoort (Chapter 5) with a brief introduction by Goldfarb and extended notes by Goldfarb (Notes A–C, K–M, O), Dreben (Notes F–I), Dreben and Goldfarb (Notes D, J, and N), and Dreben, George Huff, and Theodore Hailperin (Note E) in [Herbrand, 1971, pp. 44–202]. English translation of § 5 with a different introduction by Heijenoort and some additional extended notes by Dreben also in [Heijenoort, 1971, pp. 525–581]. (Herbrand’s PhD thesis, his cardinal work, dated April 14, 1929; submitted at the Univ. of Paris; defended at the Sorbonne June 11, 1930; printed in Warsaw, 1930.)

[Herbrand, 1968] Jacques Herbrand. Écrits Logiques. Presses Universitaires de France, Paris, 1968. Cortorted edn. of Herbrand’s logical writings by Jean van Heijenoort. Review in [Goldfarb, 1970]. English translation is [Herbrand, 1971].

[Herbrand, 1971] Jacques Herbrand. Logical Writings. Harvard Univ. Press, 1971. Ed. by Warren Goldfarb. Translation of [Herbrand, 1968] with additional annotations, brief introductions, and extended notes by Goldfarb, Burton Dreben, and Jean van Heijenoort.

(This edition is still an excellent source on Herbrand’s writings today, but it is problematic because it is based on the contorted reprint [Herbrand, 1968]. This means that it urgently needs a corrected edition based on the original editions of Herbrand’s logical writings, which are all in French and which should be included in facsimile to avoid future contortion.).

[Joshi, 1985] Aravind Joshi, editor. Proc. 9^{th} Int. Joint Conf. on Artificial Intelligence (IJCAI), 1985, Aug. 18–25, Los Angeles (CA). Morgan Kaufmann (Elsevier), Los Altos (CA), 1985. http:

//ijcai.org/Past%20Proceedings.

[Kern-Isberner & Thimm, 2012] Gabriele Kern-Isberner and Matthias Thimm. A ranking semantics for first-order conditionals. 2012. [Raedt &al., 2012, pp. 456–461]. http://dx.

doi.org/10.3233/978-1-61499-098-7-456.

[Kowalski, 1974] Robert A. Kowalski. Predicate logic as a programming language. 1974. In [Rosenfeld, 1974, pp. 569–574].

[Lambert, 1764] Johann Heinrich Lambert. Neues Organon oder Gedanken über die Erforschung und Bezeichnung des Wahren und dessen Unterscheidung von Irrthum und Schein. Johann Wendler, Leipzig, 1764. Vol. I (Dianoiologie oder die Lehre von den Gesetzen des Denkens, Alethiologie oder Lehre von der Wahrheit) (http://books.google.de/books/about/

Neues_Organon_oder_Gedanken_Uber_die_Erf.html?id=ViS3XCuJEw8C) & Vol. II (Semiotik

oder Lehre von der Bezeichnung der Gedanken und Dinge, Phänomenologie oder Lehre von

dem Schein) (http://books.google.de/books/about/Neues_Organon_oder_Gedanken_%C3%

BCber_die_Er.html?id=X8UAAAAAcAAj). Facsimile reprint by Georg Olms Verlag, Hildesheim (Germany), 1965, with a German introduction by Hans Werner Arndt.

[Liu &al., 2013] Weiru Liu, V. S. Subrahmanian, and Jef Wijsen, editors. Proc. 7^{th} Int. Conf. on Scalable Uncertainty Management (SUM 2013), Washington (DC), Sept. 16–18, 2013, number 8078 in Lecture Notes in Computer Science. Springer, 2013.

[Modgil & Prakken, 2014] Sanjay Modgil and Henry Prakken. The ASPIC^{+} framework for structured argumentation: a tutorial. Argument & Computation, 5:31–62, 2014. http://dx.

doi.org/10.1080/19462166.2013.869766.

[Poole, 1985] David L. Poole. On the comparison of theories: Preferring the most specific explanation. 1985. In [Joshi, 1985, pp. 144–147].

[Prakken & Vreeswijk, 2002] Henry Prakken and Gerhard Vreeswijk. Logics for defeasible argumentation. 2002. In [Gabbay, 2002, pp. 218–319].

[Raedt &al., 2012] Luc De Raedt, Christian Bessière, Didier Dubois, Patrick Doherty, Paolo Frasconi, Fredrik Heintz, and Peter J. F. Lucas, editors. Proc. 20^{th} European Conf. on Artificial Intelligence (ECAI), Aug. 27–31, 2012, Montepellier, France, number 242 in Frontiers in Artificial Intelligence and Applications. IOS Press, 2012. http://ebooks.iospress.nl/volume/

ecai-2012.

[Rosenfeld, 1974] Jack L. Rosenfeld, editor. Proc. of the Congress of the Int. Federation for Information Processing (IFIP), Stockholm (Sweden), Aug. 5–10, 1974. North-Holland (Elsevier), 1974.

[Simari & Loui, 1992] Guillermo R. Simari and Ronald P. Loui. A mathematical treatment of defeasible reasoning and its implementation. Artificial Intelligence, 53:125–157, 1992. Received Feb. 1990, rev. April 1991.

[Stolzenburg &al., 2003] Frieder Stolzenburg, Alejandro J. García, Carlos I. Chesñevar, and Guillermo R. Simari. Computing generalized specificity. J. Applied Non-Classical Logics, 13:87–

113, 2003. http://www.tandfonline.com/doi/abs/10.3166/jancl.13.87-113.

[Wirth & Gramlich, 1994] Claus-Peter Wirth and Bernhard Gramlich. A constructor-based approach to positive/negative-conditional equational specifications. J. Symbolic Computa-

tion, 17:51–90, 1994. http://dx.doi.org/10.1006/jsco.1994.1004, http://wirth.bplaced.
net/p/jsc94.

[Wirth & Stolzenburg, 2013] Claus-Peter Wirth and Frieder Stolzenburg. David Poole’s Specificity Revised. SEKI-Report SR–2013–01 (ISSN 1437–4447). SEKI Publications, 2013.

ii+34 pp., http://arxiv.org/abs/1308.4943.

[Wirth & Stolzenburg, 2014] Claus-Peter Wirth and Frieder Stolzenburg. David Poole’s specificity revised. 2014. In [Baral &al., 2014, pp. 168–177]. Short version of [Wirth & Stolzenburg, 2013].

[Wirth &al., 2009] Claus-Peter Wirth, Jörg Siekmann, Christoph Benzmüller, and Serge Autexier. Jacques Herbrand: Life, logic, and automated deduction. 2009. In [Gabbay & Woods, 2004ff., Vol. 5: Logic from Russell to Church, pp. 195–254].

[Wirth &al., 2014] Claus-Peter Wirth, Jörg Siekmann, Christoph Benzmüller, and Serge Autexier. Lectures on Jacques Herbrand as a Logician. SEKI-Report SR–2009–01 (ISSN 1437– 4447). SEKI Publications, 2014. Rev. edn. May 2014, ii+82 pp., http://arxiv.org/abs/0902.

4682.

[Wirth, 1997] Claus-Peter Wirth. Positive/Negative-Conditional Equations: A Constructor-Based Framework for Specification and Inductive Theorem Proving, volume 31 of Schriftenreihe Forschungsergebnisse zur Informatik. Verlag Dr. Kovač, Hamburg, 1997. PhD thesis, Univ.

Kaiserslautern, ISBN 386064551X, http://wirth.bplaced.net/p/diss.

[Wirth, 2009] Claus-Peter Wirth. Shallow confluence of conditional term rewriting systems. J.

Symbolic Computation, 44:69–98, 2009. http://dx.doi.org/10.1016/j.jsc.2008.05.005.

[Wirth, 2012] Claus-Peter Wirth. Herbrand’s Fundamental Theorem in the eyes of Jean van Heijenoort. Logica Universalis, 6:485–520, 2012. Received Jan. 12, 2012. Published online

June 22, 2012, http://dx.doi.org/10.1007/s11787-012-0056-7.

[Wirth, 2014] Claus-Peter Wirth. Herbrand’s Fundamental Theorem: The Historical Facts and their Streamlining. SEKI-Report SR–2014–01 (ISSN 1437–4447). SEKI Publications, 2014.

ii+47 pp., http://arxiv.org/abs/1405.6317.