David Poole’s Specificity Revised

Claus-Peter Wirth Frieder Stolzenburg

FB AI, Hochschule Harz, D–38855 Wernigerode, Germany

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

SEKI Report SR–2013–01

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 was internally reviewed by:

Frieder Stolzenburg FB AI, Hochschule Harz, D–38855 Wernigerode, Germany

E-mail: fstolzenburg@hs-harz.de
WWW: http://fstolzenburg.hs-harz.de

David Poole’s Specificity Revised

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

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

Searchable Online Edition, May 22, 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 ordering 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. The present means to decide our novel specificity relation, however, show only a slight improvement over the known ones for Poole’s relation, and further work is needed in this aspect.

Keywords: Artificial Intelligence, Logic Programming, Non-Monotonic Reasoning, Specificity, Defeasible Reasoning

Contents

1 Introduction 3

2 Basic Notions and Notation 4

2.1 Global Parameters for the Given Specification . . . . . . . . . . . . . . . 4

2.2 Formalization of Arguments . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.3 Notation of Concrete Examples . . . . . . . . . . . . . . . . . . . . . . . 5

2.4 Quasi-Orderings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3 Toward an Intuitive Notion of Specificity 6

3.1 Arguments as an Intuitive Abstraction . . . . . . . . . . . . . . . . . . . 6 3.2 Activation Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.3 Isolation of the Defeasible Parts of a Derivation . . . . . . . . . . . . . . 7

3.3.1 Precise Isolation in And-Trees . . . . . . . . . . . . . . . . . . . . . . 7 3.3.2 A first approximation of Activation Sets . . . . . . . . . . . . . . . . 7 3.3.3 Growth of the Defeasible Parts toward the Leaves . . . . . . . . . . . 8 3.3.4 Preference of the “More Concise” . . . . . . . . . . . . . . . . . . . . 8 3.3.5 Preference of the “More Precise” . . . . . . . . . . . . . . . . . . . . . 10 3.3.6 Conclusion on the Preferences . . . . . . . . . . . . . . . . . . . . . . 10

4 Requirements Specification of Specificity in Logic Programming 11

5 Formalizations of Specificity 12 5.1 Activation Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 5.2 Poole’s Specificity Relation P1,

and its Minor Corrections P2 and P3 . . . . . . . . . . . . . . . . . . . . 13 5.3 Our Novel Specificity Ordering CP1 . . . . . . . . . . . . . . . . . . . . . 17 5.4 Relation between the Specificity Relations P3 and CP1 . . . . . . . . . . 19

6 Putting Specificity to Test w.r.t. Human Intuition 21 6.1 Implementation of the Preference of the “More Concise” . . . . . . . . . 21 6.2 Monotonicity of the Specificity Relations w.r.t. Conjunction . . . . . . . 23 6.3 Implementation of the Preference of the “More Precise” . . . . . . . . . . 25 6.4 Conflict between the “More Concise” and the “More Precise” . . . . . . . 28 6.5 Why Global Effect matters more than Fine Structure . . . . . . . . . . . 29

7 Efficiency Considerations 30 7.1 A minor Gain in Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . 30 7.2 Comparing Derivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

7.2.1 No Pruning Required . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 7.2.2 Sets of derivations have to be compared . . . . . . . . . . . . . . . . 31 7.2.3 Path Criteria? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

8 Conclusion 33

References 34

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.

The intuitive concept of specificity plays an essential rôle in this explanation, which is most 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 or even by the human society.

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 § 4, we present a detailed analysis of the intentional motivation of our intuition that Poole’s specificity is a first step on the right way (§ 3). 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 — seems to be pretty slow.

Moreover, in § 5, we clearly disambiguate Poole’s specificity from minorly 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 minor improvements (≲_{P2}, ≲_{P3}), namely their lack of transitivity.

Furthermore, in § 6, we present several examples that will convince every carefully contemplating reader of the superiority of our novel specificity relation ≲_{CP1} w.r.t. human intuition.

Finally, we briefly discuss efficiency issues in § 7, and conclude with § 8.

2 Basic Notions and Notation

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 logic programming, as found e.g. in [Stolzenburg &al., 2003] and [Chesñevar &al., 2003].

Definition 2.1 (Literal, Rule) A literal is an atom, possibly prefixed with the symbol “¬” for negation.^{1} 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.2 (Theory, Derivation, Contradictory) 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 Π ⊢ �. Π is called contradictory if there is an atom A such that Π ⊢ {A, ¬A}; otherwise Π is non-contradictory.

Example 2.3 {A, ¬A ⇐ A} is contradictory, but {A ⇐ ¬A, ¬A ⇐ A} is noncontradictory, although we can infer both A and ¬A in classic (i.e. two-valued) logic. Our notions of consequence and consistency are equivalent both — because of the restrictiveness of our poor formal language — 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.

2.1 Global Parameters for the Given Specification

Throughout this paper, we will assume a set of literals and two sets of rules 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, and

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

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 any concrete situation.

1To distinguish this kind of negation here from default negation, the symbol “∼” is sometimes used in the literature in place of our standard symbol “¬”.

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.

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 6.10 in § 6.5.

2.2 Formalization of Arguments

There is no difference in derivation between the strict rules from Π and the defeasible rules from Δ. 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 fixed sets of rules Π and Δ, the formal definition is as simple as follows.^{4}

Definition 2.4 (Argument) (A, L) is an argument if A is a set of ground instances of rules from Δ and A∪Π ⊢ {L}.

2.3 Notation of Concrete 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.

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

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

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

bird(edna)  bird(tweety)

emu(edna)  TRUE

A2

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

It is intuitively clear here that we prefer the argument (∅, ¬flies(edna)) to the argument (A_{2}, flies(edna)), simply because the former is more specific. We will further discuss this in Example 5.16.

2.4 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.6 If ≲_{N} is a quasi-ordering, then ≈_{N} is an equivalence, <_{N} is an ordering, and ≤_{N} is a reflexive ordering.

3 Toward an Intuitive Notion 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 Lambert diagram^{5}

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

3.1 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 a derivation. Abstracting from the concrete derivation of a literal L, let us take 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.4.

3.2 Activation Sets

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. In our setting, the input consists of 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 logic programming, the only relevant property of an activation set can be the conjunction of its literals which is immediately represented by the set itself.

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. In our case, we have to exclude Π^{F} from the specification. 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 we want to compare the defeasible parts of derivations, we have to exclude the defeasible rules from Δ as well. Thus, on the one hand, all we can take into account from our specification is a subset of the general rules Π^{G}. On the other hand, it is clear that we want to have the entire set Π^{G} for our comparison of activation sets, simply because we want to base our specificity classification on our specification, namely on its general and strict part. Moreover, as will be explained in § 3.3.3, it is hardly meaningful to exclude any proper (i.e. non-literal) rule from Π^{G}. All in all, we conclude that Π^{G} is that part of our specification according to which activation sets are to be compared.

4Some authors (cf. e.g. [Stolzenburg &al., 2003], [Chesñevar &al., 2003]) require arguments to be non-contradictory w.r.t. Π, and the 1^{st} element of an argument to be ⊂-minimal w.r.t. the derivability of the 2^{nd} element. To obtain a more general setting, we omit these additional restrictions in the context of this paper. For the omission of the minimality requirement see also Corollaries 5.7 and 5.12.

5Cf. [Lambert, 1764, Dianoiologie, §§ 173–194].

Very roughly speaking, if we have fewer activation sets, then we have fewer models, which again means to have a higher specificity. Accordingly, the first straightforward sketch of a notion of specificity could 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} of (A_{1}, L_{1}), there is an activation set H_{2} ⊆ �_{H_{1}∪ Π^{G}} of (A_{2}, L_{2}) [but not vice versa].

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

3.3 Isolation of the Defeasible Parts of a Derivation

On the one hand, the argument (A, L) (described in § 3.1) is a nice abstraction from the derivation of L, because it perfectly suits our model-theoretic intentions described in § 1. By this abstraction, on the other hand, we lose the possibility to isolate the defeasible parts of the derivation more precisely.

3.3.1 Precise Isolation 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.

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

• Starting from the root of the tree, we iteratively erase all applications of strict rules. This results in 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 results in a set of trees where all nodes all of whose children are leaves result from an application of a defeasible rule.

3.3.2 A first approximation of Activation Sets

In a first approximation, we may now take all leaves of all resulting trees as the activation set for the original derivation.

3.3.3 Growth of the Defeasible Parts toward the Leaves

Note that in the set of trees resulting from the procedure described in § 3.3.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. Note that the 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].

As a consequence, in the modeling via our abstraction A, we cannot prevent the precisely isolated defeasible sub-trees resulting from the procedure described in § 3.3.1 from using the rules from Π^{G} to grow toward the root and toward the leaves again.^{6} It is clear, however, that only the growth toward the leaves can affect our activation sets and our notion of specificity.

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 what follows.

The first effect is that we immediately realize that every model of Π^{G} that is represented by the activation set { P_{i}(a) | i ∈ {0, …, n−1} } is also represented by the activation set {Q(a)}; simply because { P_{i}(a) | i ∈ {0, …, n−1} } is added to the activation sets by a growth toward the leaves, preventing that we fail to realize that an argumentation based on {Q(a)} is less (or equivalently) specific than any argumentation that gets along with { P_{i}(a) | i ∈ {0, …, n−1} }.

3.3.4 Preference of the “More Concise”

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

For instance, in our Example 2.5, an argumentation that gets along with bird(edna) is properly less specific than one that actually requires emu(edna). This effect is called^{8} preference of the “more concise”.

6Of course, our abstraction admits even different defeasible parts of a different derivation 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 identical argument (A, L). The admission of these multiple derivations is 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 express.

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

8Cf. e.g. [Stolzenburg &al., 2003, p. 94], [García & Simari, 2004, p.108].

The problem now is that the statement

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

which is required to justify the the appropriateness of this effect, is not 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 — the preference of the “more concise” can be justified by the habits of human specifiers as follows:

If human specifiers write an implication in form of a rule Q(x) ⇐ P_{0}(x)∧ ⋯ ∧P_{n−1}(x) into a specification Π of strict (i.e. non-defeasible) knowledge, then they typically intend that the implication is proper in the sense that its converse does not hold in general; otherwise they would have used an equivalence or equality symbol instead of the implication symbol, or replaced each occurrence of each Q(t) with P_{0}(t)∧ ⋯ ∧P_{n−1}(t), respectively. In particular, in our setting of logic programming — where disjunctive properties of the definition of a predicate are spread over several rules — the implications definitely tend to be proper.

Therefore, if seasoned specifiers write down such a rule, then they do not want 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)⟶

The standard example for the preference of the “more concise” is Example 6.1. It is a variation of our former Example 2.5.

Finally, let us remark that our justification for the preference of the “more concise” does not apply 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:

• the inclusion given by the rule is not generally intended (otherwise the rule should be a strict one),

• 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 a strict rule), and

• 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 6.2 to the second one.

3.3.5 Preference of the “More Precise”

By an analogous argumentation on the intentions of human specifiers, we can say that an argument that essentially requires an activation set { P_{i}(a) | i ∈ {0, …, n} } is 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}. The effect of the assumption of this intention is sometimes^{9} called preference of the “more precise”.

There is, however, an exception to be observed where this analogy does not apply, namely the case that we actually can 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, as demonstrated in Example 6.10.

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 can again justify that it is unlikely that a seasoned specifier would not have intended this non-consequence statement, namely by an argumentation analogous to the one we gave for the preference of the “more concise”. Indeed, a seasoned specifier who wants to exclude the above non-consequence would just specify a rule like

P_{j}(x) ⇐ ⋀_{i∈I} P_{i}(x),

for each j ∈ {0, …, n}\I.

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

An elementary example for the preference of the “more precise” is Example 6.5.

3.3.6 Conclusion on the Preferences

After all, even if you do not buy our justification of the preference of the “more concise” and the “more precise”, you can still follow our investigations into the properties of these preferences w.r.t. Poole’s model-theoretic notion of specificity and our correction of it in the following sections.

9Cf. e.g. [Stolzenburg &al., 2003, p. 94], [García & Simari, 2004, p.108].

4 Requirements Specification of Specificity in Logic Programming

With implicit reference to specification via (Π^{F}, Π^{G}, Δ) (cf. § 2.1), 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.4). Instead of the symbol “≲”, however, Poole [1985] uses the symbol “≤”. The standard usage of the symbol “≤” is to denote a reflexive ordering (cf. § 2.4). 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.^{10}

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.6).

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 already have an argument (A_{2}, wine) that is more specific than another argument (A_{3}, vodka), and if we come up with yet another argument (A_{1}, beer) that is even more specific than (A_{2}, wine), then, by all means, (A_{1}, beer) should be more specific than the argument (A_{3}, vodka) 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. Already in [Poole, 1985], we find an example^{11} where ≲_{P1} violates this monotonicity property of the conjunction, which is described there as “seemingly unintuitive”.^{12}

Further intricacies of computing Poole’s specificity in concrete examples are described in [Stolzenburg &al., 2003],^{13} which will make it hard to implement ≲_{P1} or its minor corrections as efficiently as required in the practice of logic programming.

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

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

12See our Example 6.3 and the references there.

13Here 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.

5 Formalizations of Specificity

5.1 Activation Sets

A generative, bottom-up (i.e. from the leaves to the root) derivation with defeasible rules can now be split into three phases of derivation of literals from literals. This splitting follows the discussion in § 3.3.1 on how to isolate the defeasible part 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 argument 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 5.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).

Roughly speaking, an argument is now more (or equivalently) specific than another one if, for each of its activation sets H_{1}, the same set H_{1} is also an activation set for the other argument. Note that we have replaced here the option of some H_{2} ⊆ �_{H_{1}∪ Π^{G}} of the first straightforward sketch for a notion of specificity displayed in § 3.2 with the more restrictive H_{2} = H_{1}. Indeed, this simplification applies here because all we consider from any activation set H in Definition 5.1 (such as H_{2} in this case) is just the closure �_{H ∪ A ∪ Π^{G}} = �_{�_{H∪Π^{G}} ∪ A ∪ Π^{G}}.

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 argumentation is completed (as can be seen in Example 6.7). 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 argumentation that is based on literals resulting from completed defeasible arguments, simply because the defeasible parts of an argumentation (as isolated in § 3.3.1) should not get more specific by the later use of additional facts that do not provide input to the defeasible parts.^{14} Note that the difference between simplified and non-simplified activation sets typically occurs in real applications, but — except Example 6.7 — not in our toy examples of § 6 designed to discuss the results of the differences in phase 1.

5.2 Poole’s Specificity Relation P1, and its Minor Corrections P2 and 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 § 4 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 5.2 (David Poole’s Original Specificity ≲_{P1}) (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 5.3 (Standard Version of David Poole’s Specificity ≲_{P2}) (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 5.3 as compared to Definition 5.2 is that “(A_{2}, L_{1})” is replaced with “(∅, L_{1})”. We did not encounter any example yet where this most appropriate correction of the counter-intuitive variant “(A_{2}, L_{1})” of Definition 5.2 makes any difference to today’s standard “(∅, L_{1})” in Definition 5.3, and leave it as an exercise to construct one.

14We 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; e.g. by presenting 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.

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 5.4.

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

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

drink  beer

thirst  TRUE

A1

Let us compare the specificity of the arguments (A_{1}, beer) and (∅, drink). We have �_{Π_{5.4}} = {thirst, drink}, �_{Π_{5.4}∪Δ_{5.4}} = {beer} ∪ �_{Π_{5.4}}. We have (A_{1}, beer) ≲_{P2} (∅, drink) because for every H ⊆ �_{Π_{5.4}∪Δ_{5.4}} that is a simplified activation set for (A_{1}, 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_{1}, 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 (A_{1}, beer) ≈_{P2} (∅, drink), although (∅, drink) <_{P3} (A_{1}, beer) must be given according to intuition, because, if beer produces a conflict with our drinking habits, there is no reason to prefer it to another drink. Finally note that by Corollary 5.6, we will get (A_{1}, beer) ≈_{P1} (∅, drink) as well.

To overcome this minor flaw, we finally add an implication as an additional requirement in Definition 5.5. This implication guarantees that no argument that requires defeasible rules can be more specific than an argument that does not require any defeasible rules at all.

Definition 5.5 (Rather Unflawed Version of David Poole’s Specificity ≲_{P3}) (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]^{15} 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}).

As every simplified activation set that passes the condition of Definition 5.2 also passes the one of Definition 5.3, we get the following corollary of our three definitions.

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

Corollary 5.7 If (A_{1}, L_{1}), (A_{2}, L_{2}) are arguments and we have A_{1} ⊆ A_{2} and L_{1} = L_{2}, then we have (A_{1}, L_{1}) ≲_{P3} (A_{2}, L_{2}) .

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

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

in Definition 5.5 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.

15

Example 5.8 (Counterexample to the Transitivities)

Π_{5.8}^{F} := \{ \begin{matrix}alcohol, \\ blessing, \\ thirst \end{matrix} \} ,
Π_{5.8}^{G} := { wine ⇐ e } ,
Δ_{5.8} := A_{1} ∪ A_{2} ∪ A_{3},
A_{1} := \{ \begin{matrix}e ← alcohol∧blessing∧thirst, \\ beer ← e \end{matrix} \} ,
A_{2} := { wine ← alcohol∧blessing } ,
A_{3} := { vodka ← alcohol } .

Compare the specificity of the arguments (A_{1}, beer), (A_{2}, wine), (A_{3}, vodka) !

vodka  wine  wine  beer

e

alcohol  blessing  thirst

A_{1} TRUE A1 A1 A1 A2 A2 A3

Lemma 5.9 There are

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

• arguments (A_{1}, L_{1}), (A_{2}, L_{2}), (A_{3}, L_{3}) with respectively minimal sets A_{1}, A_{2}, A_{3} (i.e., (A′_{i}, L_{i}) is not an argument for any proper subset A′_{i} ⊊ A_{i}),

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}).

Proof of Lemma 5.9

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

�_{Π_{5.8}} = {alcohol, blessing, thirst}, �_{Π_{5.8}∪Δ_{5.8}} = {e, beer, wine, vodka} ∪ �_{Π_{5.8}}.

Thus, regarding the arguments (A_{1}, beer), (A_{2}, wine), (A_{3}, vodka), the additional implication condition of Definition 5.5 as compared to Definitions 5.2 and 5.3 is always satisfied, simply because its condition is always false.

\underline{(A_{3}, vodka) ≵_{P1} (A_{1}, beer) ≲_{P3} (A_{2}, wine) :} The minimal simplified activation sets for

(A_{1}, beer) that are subsets of �_{Π_{5.8}∪Δ_{5.8}} and no

simplified activation sets for (∅, beer) (or, without any difference, no simplified activation set for (A_{3}, beer)) are {alcohol, blessing, thirst} and {e}, which are simplified activation sets for (A_{2}, wine) — but {e} is no simplified activation set for (A_{3}, vodka).

\underline{(A_{1}, beer) ≵_{P1} (A_{2}, wine) ≲_{P3} (A_{3}, vodka) :} The only minimal simplified activation set for

(A_{2}, wine) that is a subset of �_{Π_{5.8}∪Δ_{5.8}} and no

simplified activation set for (∅, wine) (such as {e}) (or, without any difference, no simplified activation set for (A_{1}, wine)) is {alcohol, blessing}, which is a simplified activation set for (A_{3}, vodka), but not for (A_{1}, beer).

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

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

(A_{2}, vodka) is {alcohol}, which is not a simplified activation set for (A_{2}, wine). Q.e.d. (Lemma 5.9)

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

Theorem 5.10 There is a specification (Π_{5.8}^{F}, Π_{5.8}^{G}, Δ_{5.8}), such that Π_{5.8}^{F} ∪ Π_{5.8}^{G} ∪ Δ_{5.8} is non-contradictory, but none of ≲_{P1}, ≲_{P2}, ≲_{P3}, <_{P1}, <_{P2}, <_{P3} is transitive. Moreover, all counterexamples to transitivity can be restricted to arguments with minimal sets of ground instances of defeasible rules.

As a consequence of Theorem 5.10, the respective relations in [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 ⪰ [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 5.8, 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]. According 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 5.6, 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 5.9 and Corollary 5.6 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}).

5.3 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 5.8) hidden and even denied formal deficiency of these relations, namely their lack of transitivity.

Please keep in mind, however, that our true motivation for overcoming this deficiency by 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 even more clear in § 6 than in § 3.

Therefore, in this section, 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 5.11 (Our version of Specificity ≲_{CP1}) (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]^{16} activation set for (A_{1}, L_{1}) is also an activation set for (A_{2}, L_{2}).

The crucial change in Definition 5.11 as compared to Definition 5.5 is not the merely technical emphasis it puts on the case “L_{1} ∈ �_{Π}”, which has no effect on the extension of the relation as compared to ≲_{P3}. The crucial changes actually are

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

(B) omission of the previously technically required,^{17} 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 § 5.1, is the one from simplified to (non-simplified) activation sets.

Corollary 5.12 If (A_{1}, L_{1}), (A_{2}, L_{2}) are arguments and we have A_{1} ⊆ A_{2} and L_{1} = L_{2}, then we have (A_{1}, L_{1}) ≲_{CP1} (A_{2}, L_{2}) .

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

17See the discussion in Example 6.5 on why this condition is technically required for P1, P2, and P3.

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

Proof of Theorem 5.13

≲_{CP1} is a reflexive relation on arguments because of Corollary 5.12.

To show transitivity, let us assume

(A_{1}, L_{1}) ≲_{CP1} (A_{2}, L_{2}) ≲_{CP1} (A_{3}, L_{3}).

According to Definition 5.11, 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 5.11 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 5.13)

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 5.14 If �_{Π} is finite, then <_{CP1} is well-founded.

5.4 Relation between the Specificity Relations P3 and CP1

Theorem 5.15

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

Set Π^{≥2} to 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 § 5.1, but not w.r.t. phase 3 in addition, then the condition of Theorem 5.15 would not have been required at all. 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 § 5.3.

Proof of Theorem 5.15

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 �_{�∪Π} ⊆ T_{�∪ �_{Π^{<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 (A_{1}, L_{1}) ≲_{CP1} (A_{2}, L_{2}) under condition 1 and the initial 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} ∈ �∪ �_{Π}, and 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, an activation set for (A_{2}, L_{2}), as was to be shown for our only remaining sub-claim. Q.e.d. (Theorem 5.15)

Finally, with the help of Theorem 5.15, we can now analyze Example 2.5, and also check how our relation CP1 behaves in case of our counterexample for transitivity:

Example 5.16 (Example 1 of [Poole, 1985]) (continuing Example 2.5) We have (A_{2}, flies(edna)) ≴_{CP1} (∅, ¬flies(edna))

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

We have (∅, ¬flies(edna)) ≲_{P3} (A_{2}, flies(edna)), because ¬flies(edna) ∈ �_{Π_{2.5}} and because the premise of the last condition in Definition 5.5 is contradictory for A_{1} := ∅, and cannot be satisfied by any set H ⊆ �_{Π_{2.5}∪Δ_{2.5}}. All in all, by Theorem 5.15 (where condition 4 is satisfied),

we get (∅, ¬flies(edna))<_{CP1}(A_{2}, flies(edna))
and (∅, ¬flies(edna)) <_{P3} (A_{2}, flies(edna)).

Example 5.17 (continuing Example 5.8) The following holds for our specification of Example 5.8 by Lemma 5.9 and Corollary 5.6:

(A_{1}, beer) <_{P3} (A_{2}, wine) <_{P3} (A_{3}, vodka) ≵_{P3} (A_{1}, beer).

We have now:

(A_{1}, beer) <_{CP1} (A_{2}, wine) <_{CP1} (A_{3}, vodka) >_{CP1} (A_{1}, beer)

simply because the trouble-making set {e} is not to be considered here: it is not a subset of �_{Π_{5.8}} at all! The checking of the details is left to the reader. Note that, because of Lemma 5.9, Theorem 5.15 (where condition 4 is satisfied), Theorem 5.13, and Corollary 2.6, all that is actually left to show is

(A_{1}, beer) ≵_{CP1} (A_{2}, wine) ≵_{CP1} (A_{3}, vodka).

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

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

Note that we can freely apply Theorem 5.15 because at least one^{18} of its conditions is satisfied in all the following examples except Example 6.8, which is the only example where we have an activation set that is actually not a simplified one.

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

6.1 Implementation of the Preference of the “More Concise”

First let us see what happens to Example 6.1 if we are not so certain anymore whether no emu can fly.

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

Π_{6.1}^{F} := Π_{2.5}^{F}
Π_{6.1}^{G} := { bird(x) ⇐ emu(x) } ,
Δ_{6.1} := \{ \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)

emu(edna)  TRUE

A2

A1

Let us compare the specificity of the arguments (A_{1}, ¬flies(edna)) and (A_{2}, flies(edna)). We have �_{Π_{6.1}} = {bird(tweety), emu(edna), bird(edna)}, �_{Π_{6.1}∪Δ_{6.1}} = {¬flies(edna), flies(edna), flies(tweety)} ∪ �_{Π_{6.1}}.

We have (A_{2}, flies(edna)) ≴_{CP1} (A_{1}, ¬flies(edna)) because flies(edna) ∉ �_{Π_{6.1}} and because {bird(edna)} ⊆ �_{Π_{6.1}} 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) ∉ �_{Π_{6.1}} and because, if H ⊆ �_{Π_{6.1}∪Δ_{6.1}} 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 5.15, we get (A_{1}, ¬flies(edna))<_{CP1}(A_{2}, flies(edna)) and (A_{1}, ¬flies(edna)) <_{P3} (A_{2}, flies(edna)).

18Condition 4 of Theorem 5.15 is satisfied for Examples 6.1, 6.2, 6.5, and 6.10. Condition 3 (but not condition 4) is satisfied for Examples 6.3, 6.4, 6.6, 6.7 and 6.9.

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

Π_{6.2}^{F} := { emu(edna) } ,  Π_{6.2}^{G} := ∅,
Δ_{6.2} := \{ \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)

emu(edna)  TRUE

A2

A2

A1

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

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

Now, however, we have (A_{2}, flies(edna)) ≲_{CP1} (A_{1}, ¬flies(edna)) because ¬flies(edna) ∉ �_{Π_{6.2}} and, for every activation set H ⊆ �_{Π_{6.2}} 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 still have (A_{2}, flies(edna)) ≴_{P3} (A_{1}, ¬flies(edna)), because {bird(edna)} ⊆ �_{Π_{6.2}∪Δ_{6.2}} 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) ∉ �_{Π_{6.2}} and because, if H ⊆ �_{Π_{6.2}∪Δ_{6.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)). All in all, by Theorem 5.15, this time 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 a defeasible rule instance such as bird(edna) ← emu(edna) to reduce the specificity of A_{2} 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? According to human intuition, this question has a negative answer, as we have already explained at the end of § 3.3.4. Moreover, Example 6.3 will exhibit a strong reason to deny it. Finally, see Example 6.6 for another example that makes even clearer why defeasible rules should be considered for their global semantical effect instead of their syntactical fine structure.

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

Monotonicity w.r.t. conjunction is the following property for a binary relation R on arguments: 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}).

This property is obviously given for all of ≲_{CP11}, <_{CP11}, ≈_{CP11} 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′_{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}) (which implies L′_{1} ∉ �_{Π}), however, monotonicity can be expected in general neither for ≲_{CP11}, nor for <_{CP11}, simply because then we get L′_{1} ∉ �_{Π}, but do not necessarily have activation set for L_{2}^{3−i}. This non-monotonicity, however, is part and parcel of our decision to consider arguments whose literals are elements of �_{Π} to be the most specific ones.

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]:

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

Π_{6.3}^{F} := \{ \begin{matrix}a, \\ d \end{matrix} \} ,
Π_{6.3}^{G} := \{ \begin{matrix}g_{1} ⇐ ¬c∧¬f, \\ g_{2} ⇐ c∧f \end{matrix} \} ,
Δ_{6.3} := 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

a  TRUE  d A2 A2 A1 A2 A2 A1

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

�_{Π_{6.3}} = {a, d} �_{Π_{6.3}∪Δ_{6.3}} = {b, c, e, f, g_{1}, g_{2}, ¬c, ¬f} ∪ �_{Π_{6.3}}.

We have (A_{1}, g_{1}) ≈_{CP1} (A_{2}, g_{2}) because H ⊆ �_{Π_{6.3}} 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} ⊆ �_{Π_{6.3}∪Δ_{6.3}} is a simplified activation set for (A_{1}, g_{1}), but neither for (∅, g_{1}), nor for (A_{2}, g_{2}). {a, f} ⊆ �_{Π_{6.3}∪Δ_{6.3}} 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 in the isomorphic sub-specification of Example 6.2, 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 § 4, the conjunction of two respectively more specific derivations should be more specific, shouldn’t it? On the other hand, considering ≲_{CP1} instead of ≲_{P3}, the conjunction of two equivalently specific derivations results in an equivalently specific derivation — exactly as one intuitively expects.

24

Example 6.4 (1^{st} Variation of Example 6.3)

Π_{6.4}^{F} := Π_{6.3}^{F},
Π_{6.4}^{G} := \{ \begin{matrix}g_{1} ⇐ ¬c∧¬f, \\ g_{2} ⇐ c∧f, \\ b ⇐ a \end{matrix} \} ,
Δ_{6.4} := 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

a  TRUE  d A2 A1 A2 A2 A1

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

�_{Π_{6.4}} = {a, b, d} �_{Π_{6.4}∪Δ_{6.4}} = {c, e, f, g_{1}, g_{2}, ¬c, ¬f} ∪ �_{Π_{6.4}}.

We now have (A_{2}, g_{2}) ≴_{CP1} (A_{1}, g_{1}) because {b, d} ⊆ �_{Π_{6.4}} is an activation set for (A_{2}, g_{2}), but not for (A_{1}, g_{1}). We still have (A_{1}, g_{1}) ≲_{CP1} (A_{2}, g_{2}) because, for any activation set H ⊆ �_{Π_{6.4}} for (A_{1}, g_{1}), we have {a, b} ⊆ 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 6.3. Thus, the situation for ≲_{P3} is just as in Example 6.3, 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 element, respectively, should be more specific. Indeed, from the isomorphic sub-specifications in Examples 6.1 and 6.2, we know that (A_{1}, ¬c) <_{CP1} (A_{2}, c) and (A_{1}, ¬f) ≈_{CP1} (A_{2}, f), respectively. All in all, Poole’s specificity relation ≲_{P3} fails in this example again, whereas the quasiordering ≲_{CP1} works according to human intuition and satisfies the required monotonicity w.r.t. conjunction of § 4. Moreover, this holds for all of ≲_{CP11}, <_{CP11}, ≈_{CP11} in all specificiations, with the only exception of the borderline case discussed at the beginning of § 6.2.

6.3 Implementation of the Preference of the “More Precise”

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

Example 6.5

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

¬lovely  lovely

grandpa  grandma

noisy  TRUE  somebody

A1

A1

A2

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

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

We have (A_{2}, lovely)≴_{CP1}(A_{1}, ¬lovely) because lovely ∉ �_{Π_{6.5}} and because {somebody} ⊆ �_{Π_{6.5}} 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 ∉ �_{Π_{6.5}} and because, if H ⊆ �_{Π_{6.5}∪Δ_{6.5}} 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 5.15, 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 5.5. 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.

So both relations ≲_{P3} and ≲_{CP1} produce the intuitive result if the “more precise” superconjunction is directly the condition of a rule. Let us see whether this is also the case if the condition of the rule is only derived from a super-conjunction.

Example 6.6 (2^{nd} Variation of Example 6.3)

Π_{6.6}^{F} := \{ \begin{matrix}a, \\ d \end{matrix} \} ,
Π_{6.6}^{G} := \{ \begin{matrix}g_{1} ⇐ ¬c, \\ g_{2} ⇐ c∧f \end{matrix} \} ,
Δ_{6.6} := 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

a  TRUE  d A2 A2 A1 A2 A2

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

�_{Π_{6.6}} = {a, d} �_{Π_{6.6}∪Δ_{6.6}} = {b, c, e, f, g_{1}, g_{2}, ¬c} ∪ �_{Π_{6.6}}.

We have (A_{1}, g_{1}) ≴_{CP1} (A_{2}, g_{2}) because {a} ⊆ �_{Π_{6.6}} 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 �_{Π_{6.6}} includes a, and so is also an activation set for (A_{1}, g_{1}). Considering Theorem 5.15 and the the activation set {b, d} for (A_{2}, g_{2}), we see (A_{1}, g_{1}) △_{P3} (A_{2}, g_{2}). All in all, only ≲_{CP1} realizes — via (A_{2}, g_{2}) <_{CP1} (A_{1}, g_{1}) — 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.2, this example shows again that ≲_{P3} does not really implement the intuition that defeasible rules should be considered for their global semantical effect instead of their syntactical fine structure.

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

Π_{6.7}^{F} := \{ \begin{matrix}c, \\ d, \\ e \end{matrix} \} ,
Π_{6.7}^{G} := { x ⇐ a∧f } ,
Δ_{6.7} := 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

a  c  TRUE b  f

d  ¬x  e A1 A1 A1 A2 A2 A3 A4 A5

Let us 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).

�_{Π_{6.7}} = {c, d, e}, �_{Π_{6.7}∪Δ_{6.7}} = {a, b, f, x, ¬x} ∪ �_{Π_{6.7}}.

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 ∉ �_{Π_{6.7}}, and because any activation set H ⊆ �_{Π_{6.7}} 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.^{19} 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 (implicitly via {d, f} ⊆ �_{Π_{6.7}∪Δ_{6.7}}) the defeasible rule of A^{3}, which is not part of any of the two arguments under comparison. 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 �_{Π∪Δ}. This means in particular that 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}.

27

Example 6.8 (Variation of Example 6.7)

Π_{6.8}^{F} := \{ \begin{matrix}c, \\ d, \\ e \end{matrix} \} ,
Π_{6.8}^{G} := \{ \begin{matrix}x ⇐ a∧f, \\ f ⇐ e \end{matrix} \} ,
Δ_{6.8} := 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

a  c  TRUE b  f

d  ¬x  e A1 A1 A1 A2 A2 A4 A5

Let us compare the specificity of the arguments (A^{1}∪A^{4}∪A^{5}, x), (A^{2}∪A^{4}∪A^{5}, ¬x), (A^{4}, x).

�_{Π_{6.8}} = {c, d, e, f}, �_{Π_{6.8}∪Δ_{6.8}} = {a, b, x, ¬x} ∪ �_{Π_{6.8}}.

Obviously, x, ¬x ∉ �_{Π_{6.8}}. Moreover, {d} ⊆ �_{Π_{6.8}} is an activation set for (A^{4}, x) (but not a simplified one!) and, a fortiori (by Corollary 5.12), for (A^{1}∪A^{4}∪A^{5}, x), but not for (A^{2}∪A^{4}∪A^{5}, ¬x). Furthermore, every activation set H ⊆ �_{Π_{6.8}} 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). Furthermore, every activation set H ⊆ �_{Π_{6.8}} 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 equivalent to (A^{4}, x).

Moreover, c∧d∧e is not essentially required for (A^{1}∪A^{4}∪A^{5}, x), and so this argument is equivalent to (A^{4}, x). The reason for this remarkable effect is not the lack of ⊂-minimality of A^{1}∪A^{4}∪A^{5} for deriving x, but the semantic, model-theoretic approach, which simply ignores the fact that the derivation via A^{1} requires the more precise activation set. Indeed, primarily we 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.^{20} This means that ≲_{P3} fails here completely w.r.t. Poole’s intuition, as actually in most non-trivial examples.

19Because {d, f} ⊆ �_{Π_{6.7}∪Δ_{6.7}} 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 5.15. Because {b, c, d} ⊆ �_{Π_{6.7}∪Δ_{6.7}} 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).

20The 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}.

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

Example 6.9 (Variation of Example 6.4)

Π_{6.9}^{F} := Π_{6.3}^{F},
Π_{6.9}^{G} := \{ \begin{matrix}g_{1} ⇐ ¬c, \\ g_{2} ⇐ c∧f, \\ b ⇐ a \end{matrix} \} ,
Δ_{6.9} := 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

a  TRUE  d A2 A1 A2 A2

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

�_{Π_{6.9}} = {a, b, d}, �_{Π_{6.9}∪Δ_{6.9}} = {c, e, f, g_{1}, g_{2}, ¬c} ∪ �_{Π_{6.9}}.

We now have (A_{1}, g_{1}) △_{CP1} (A_{2}, g_{2}) for the following reasons: {a} ⊆ �_{Π_{6.9}} is an activation set for for (A_{1}, g_{1}), but not for (A_{1}, g_{1}); {b, d} ⊆ �_{Π_{6.9}} is an activation set for (A_{2}, g_{2}), but not for (A_{2}, g_{2}). By Theorem 5.15 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.

6.5 Why 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 6.10 (Example from Page 95 of [Stolzenburg &al., 2003])

Π_{6.10}^{F} := { q(a) } ,
Π_{6.10}^{G} := { s(x) ⇐ q(x) } ,
Δ_{6.10} := \{ \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)

TRUE  q(a) A1 A1 A2

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

�_{Π_{6.10}} = {q(a), s(a)}, �_{Π_{6.10}∪Δ_{6.10}} = {p(a), ¬p(a)} ∪ �_{Π_{6.10}}.

We have (A_{1}, ¬p(a)) ≈_{P3} (A_{2}, p(a)), because of p(a), ¬p(a) ∉ �_{Π_{6.10}}, and because, for H ⊆ �_{Π_{6.10}∪Δ_{6.10}}, 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 5.15, 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 Π_{6.10}^{G}. Note that nothing is changed here if s(x) ⇐ q(x) is replaced by setting Π_{6.10}^{G} := {s(a)}. If s(x) ⇐ q(x) is replaced by setting Π_{6.10}^{G} := ∅ and Π_{6.10}^{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 to Π^{G}.^{21}

21Cf. Note 3.

7 Efficiency Considerations

The definitions of specificity we have presented in this paper (in particular, Definition 5.5 according to [Simari & Loui, 1992] and Definition 5.11) share several features, which we will highlight in this section.

7.1 A minor Gain in Efficiency

As a straightforward procedure for deciding the specificity orderings ≲_{CP1} and ≲_{P3} between two arguments has 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 in principle each possible subset has to be tested.

7.2 Comparing Derivations

To lower the computational complexity, more syntactic criteria for computing specificity are introduced in [Stolzenburg &al., 2003]. These criteria refer to the derivations for the given arguments.

A more formal definition of the and-trees of § 3.3.1 may be appropriate here:

Definition 7.1 (Derivation Tree) Let a defeasible specification (Π^{F}, Π^{G}, Δ) and a literal h be given. A derivation tree T for h w.r.t. the specification is a finite, rooted tree where all nodes are labeled with literals, satisfying the following conditions:

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

2. For each node N in T that is labeled with the literal L, there is a strict or defeasible rule in Π ∪ Δ with head L_{0} and body L_{1}∧ ⋯ ∧L_{k}, such that L = L_{0}σ for some substitution σ, and the node N has exactly k child nodes, which are labeled with L_{1}σ, …, L_{k}σ, respectively.

7.2.1 No Pruning Required

The concept of pruning derivation 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 ∈ �_{Π∪Δ}\�_{Π}. Because this is not possible with the relation ≲_{CP1}, this problem vanishes with our new version of specificity. See also Example 6.7.

7.2.2 Sets of derivations have to be compared

Yet still, the new relation ≲_{CP1} inherits several properties from ≲_{P3}. For instance, in general the syntactic criterion requires us to compare sets of derivations. This is true for both versions of the specificity relation, which can be seen from Example 7.2.

Example 7.2

Π_{7.2}^{F} := \{ \begin{matrix}a, \\ e \end{matrix} \} ,

Π_{7.2}^{G} := \{ \begin{matrix}d ⇐ c_{1}, \\ d ⇐ c_{2}, \\ c_{1} ⇐ b, \\ c_{2} ⇐ b \end{matrix} \} ,

Δ_{7.2} := \{ \begin{matrix}b ← a, \\ ¬f ← d, \\ f ← d∧e \end{matrix} \} ,
A^{1} := \{ \begin{matrix}f ← d∧e, \\ b ← a \end{matrix} \} ,
A^{2} := \{ \begin{matrix}¬f ← d, \\ b ← a \end{matrix} \} .

f  ¬f

d  d

e  c_{1}  c_{2}

b

TRUE  a A1 A1 A2 A1∩A2

We have (A^{1}, f) <_{P3} (A^{2}, ¬f) and (A^{1}, f) <_{CP1} (A^{2}, ¬f). There are two derivation and-trees for each argument. Since either c_{1} or c_{2} is in the derivation tree, a one-to-one comparison of derivations does not suffice.

The reason for this complication is that we consider a very general setting of defeasible reasoning in this paper, because we admit

1. more than one antecedent in rules, i.e. bodies containing more than one (possibly negative) literal, and

2. (possibly) non-empty sets of background knowledge, i.e. strict rules, not only facts.

In the literature, often restricted cases are considered only: antecedents are always singletons in [Gelfond & Przymusinska, 1990], no background knowledge is allowed in [Dung & Son, 1996], and both restrictions are present in [Benferhat & Garcia, 1997].

7.2.3 Path Criteria?

As the computation of activations sets via goal-directed derivations from [Stolzenburg &al., 2003, § 3.3] is hardly changed by our step from ≲_{P3} to ≲_{CP1}, let us have a closer look here only at the path criterion of [Stolzenburg &al., 2003, § 3.4].

Definition 7.3 (Path) For a leaf node N in a derivation 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 7.4 ([Stolzenburg &al., 2003, Definition 23]) T_{1} ⊴ T_{2} if T_{1} and T_{2} are two derivation 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 derivation trees can be compared w.r.t. ⊴ efficiently. This requires the pairwise comparison of all nodes in the trees for each path. Hence, the respective complexity is polynomial, at most O(n^{3} log n), where n is the overall number of nodes, which makes the relation ⊴ attractive for practical use.

Definition 7.5 ([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 derivation tree T_{1} for h_{1} there is a derivation tree T_{2} for h_{2} such that T_{1} ⊴ T_{2}.

It is shown in [Stolzenburg &al., 2003, Theorem 25] that in special cases, ≤ and ≲_{P2} are equivalent, namely if the arguments involved in the comparison correspond to exactly one derivation 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 addition restriction of Definition 5.5 as compared to Definition 5.3; so we also get ≤ ⊆ ≲_{P3}. Finally, we can apply Theorem 5.15 and so get the intended ≤ ⊆ ≲_{CP1}, but only with the strong restriction of the condition of Theorem 5.15. We see no way yet to relax this restriction resulting from phase 3 of § 5.1.

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

Example 7.6

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

¬d  d

c_{2}  c_{1}

a  TRUE  b A{2 \atop 7.6} A{2 \atop 7.6} A{1 \atop 7.6} A{1 \atop 7.6} A{1 \atop 7.6}

We have (A_{7.6}^{1}, d) △_{P3} (A_{7.6}^{2}, ¬d) and (A_{7.6}^{1}, d) <_{CP1} (A_{7.6}^{2}, ¬d). Both arguments (A_{7.6}^{1}, d) and (A_{7.6}^{2}, ¬d) correspond to exactly one derivation 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_{7.6}^{1}, d) ≤ (A_{7.6}^{2}, ¬d) does not hold.

8 Conclusion

We would need further discussions on our utmost surprising new findings — 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}. Only under the condition of Theorem 5.15, the transitive closure of ≲_{P3} is a subset of ≲_{CP1}, and therefore a possible choice. Moreover, it will still have all the intuitive shortcomings made obvious in § 6. We do not see how this transitive closure could be decided efficiently. Furthermore, this 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.

Finally, contrary to the transitive closure of ≲_{P3}, our novel relation ≲_{CP1} also solves the problem of non-monotonicity of specificity w.r.t. conjunction (cf. § 6.2), which was already realized as a problem of ≲_{P1} by Poole [1985] (cf. Example 6.3).

The present means to decide our novel specificity relation ≲_{CP1}, however, show improvements (cf. §§ 7.1 and 7.2.1) and setbacks (cf. § 7.2.3) if compared to the known ones for Poole’s relation. Further work is needed to improve efficiency considerably. Our plan is to narrow the concept of ≲_{CP1} further down according to § 3, and then to develop strong methods for efficient operationalization, which can hardly be found for any of ≲_{P1}, ≲_{P2}, ≲_{P3}, ≲_{CP1}.

It is just too early for a further conclusion, 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.

Acknowledgments

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

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} Int. Conf. on Principles of Knowledge Representation and Reasoning, 1996, Nov. 5–8, Cambridge (MA). Morgan Kaufmann, Los Altos (CA) (Elsevier), 1996.

[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.

[Chesñevar &al., 2003] Charlos 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.

[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].

[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.

[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.

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

sevier), 1985. http://ijcai.org/Past%20Proceedings.

[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.

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

[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, Charlos 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.