Read anywhere, anytime

Grigoris Antoniou - Iddu

English

23 Pages

Read

Downloading requires you to have access to the YouScribe library

__
Learn all about the services we offer
__

Description

A Tutorial on Default LogicsGRIGORIS ANTONIOUGriffith UniversityDefault Logic is one of the most prominent approaches to nonmonotonic reasoning,and allows one to make plausible conjectures when faced with incompleteinformation about the problem at hand. Default rules prevail in many applicationdomains such as medical diagnosis and legal reasoning.Several variants have been developed over the past years, either to overcome someperceived deficiencies of the original presentation, or to realize somewhat differentintuitions. This paper provides a tutorial-style introduction to some importantapproaches of Default Logic. The presentation is based on operational models forthese approaches, thus making them more easily accessible to a broader audience,and more easily usable in practical applications.Categories and Subject Descriptors: I.2.3 [Artificial Intelligence]: Deduction andTheorem Proving—Nonmonotonic reasoning and belief revision; I.2.4 [ArtificialIntelligence]: Knowledge Representation Formalisms andMethods—Representation languagesGeneral Terms: Languages, TheoryAdditional Key Words and Phrases: Default Logic, nonmonotonic reasoning,operational models1. INTRODUCTION: DEFAULT REASONING data. Classical logic indeed has the ca-pacity to represent and reason with cer-When an intelligent system (either com-tain aspects of incomplete information.puter-based or human) tries to solve aBut there are occasions where addi-problem, it may be able to rely ...

Subjects

Informations

Published by | Iddu |

Reads | 40 |

Language | English |

Report a problem

GRIGORIS ANTONIOU

Griffith University

Default Logic is one of the most prominent approaches to nonmonotonic reasoning,

and allows one to make plausible conjectures when faced with incomplete

information about the problem at hand. Default rules prevail in many application

domains such as medical diagnosis and legal reasoning.

Several variants have been developed over the past years, either to overcome some

perceived deficiencies of the original presentation, or to realize somewhat different

intuitions. This paper provides a tutorial-style introduction to some important

approaches of Default Logic. The presentation is based on operational models for

these approaches, thus making them more easily accessible to a broader audience,

and more easily usable in practical applications.

Categories and Subject Descriptors: I.2.3 [Artificial Intelligence]: Deduction and

Theorem Proving—Nonmonotonic reasoning and belief revision; I.2.4 [Artificial

Intelligence]: Knowledge Representation Formalisms and

Methods—Representation languages

General Terms: Languages, Theory

Additional Key Words and Phrases: Default Logic, nonmonotonic reasoning,

operational models

1. INTRODUCTION: DEFAULT REASONING data. Classical logic indeed has the ca-

pacity to represent and reason with cer-

When an intelligent system (either com-

tain aspects of incomplete information.

puter-based or human) tries to solve a

But there are occasions where addi-

problem, it may be able to rely on com- tional information needs to be “filled in”

plete information about this problem, to overcome the incompleteness, be-

and its main task is to draw the correct cause certain decisions must be made.

conclusions using classical reasoning. In In such cases the system has to make

such cases, classical predicate logic may some plausible conjectures, which in the

be sufficient. case of default reasoning are based on

However, in many situations the sys- rules of thumb, called defaults. For ex-

tem has only incomplete information at ample, an emergency doctor has to

hand, be it because some pieces of infor- make some conjectures about the most

mation are unavailable, or because it probable causes of the symptoms ob-

has to respond quickly and does not served. Obviously, it would be inappro-

priate to await the results of possiblyhave the time to collect all relevant

Author’s address: School of Computing & Information Technology, Griffith University, Brisbane, QLD

4111, Australia; email: ga@cit.gu.edu.au.

Permission to make digital/hard copy of part or all of this work for personal or classroom use is granted

without fee provided that the copies are not made or distributed for profit or commercial advantage, the

copyright notice, the title of the publication, and its date appear, and notice is given that copying is by

permission of the ACM, Inc. To copy otherwise, to republish, to post on servers, or to redistribute to

lists, requires prior specific permission and/or a fee.

© 2000 ACM 0360-0300/99/0900–0337 $5.00

ACM Computing Surveys, Vol. 31, No. 3, September 1999338 • G. Antoniou

CONTENTS actually, we can talk about a family of

default reasoning methods because they

1. Introduction: Default Reasoning

share the same foundations.2. Default Logic

In this paper we present the motiva-2.1 The Notion of a Default

2.2 The Syntax of Logic tions and basic ideas of some of the

2.3 Informal Discussion of the Semantics most important default logic variants,

2.4 An Operational Definition of Extensions

and compare them both with respect to

2.5 Some Examples

interconnections and the fulfillment of2.6 Reiter’s Original Definition of Extensions

3. Properties of Default Logic some properties. When designing a tuto-

3.1 Existence of Extensions rial, it is good to have some aims

3.2 Joint Consistency of Justifications against which the final product can be

3.3 Cumulativity and Lemmas

tested. The particular aims of this tuto-4. Justified Default Logic

rial paper are the following:4.1 Motivation and Formal Presentation

4.2 Lukaszewicz’ Original Definition

5. Constrained Default Logic —To present the basic ideas of Default

5.1 Motivation and Definition Logic to persons without prior knowl-

5.2 A Fixpoint Characterization

edge in the area. Only basic under-

5.3 Interconnections

standing of classical logic is required.6. Priorities on Defaults

6.1 Motivation

—To equip the reader with skills and6.2 Static Priorities

6.3 Dynamic methods so that they can apply the

7. Other Variants of Default Logic concepts of Default Logic to concrete

7.1 Rational Default Logic

situations. This is achieved by the use

7.2 Cumulative Default Logic

of operational models which can be7.3 Disjunctive Logic

7.4 Weak Extensions applied in a straightforward manner

8. Conclusion to examples without having to make

any guesses, as is the case with the

usual fixpoint or quasiinductive defi-

nitions.

extensive and time-consuming tests be-

—To give the reader a sense of thefore beginning with treatment.

diversity of the topic.When decisions are based on assump-

tions, these may turn out to be wrong in

The paper is organized as follows: Sec-

the face of additional information that

tion 2 presents the basics of Reiter’s

becomes available; i.e., medical tests

Default Logic. Section 3 discusses prop-

may lead to a modified diagnosis. The

erties and design decisions of this ap-

phenomenon of having to take back

proach, and outlines some alternative

some previous conclusions is called non-

intuitions on these issues. Sections 4–6

monotonicity; it says that if a statement

describe some basic default logic vari-

w follows from a set of premises M and ants: Justified Default Logic [Lukasze-

M # M9, w does not necessarily follow wicz 1988], Constrained Default Logic

from M9. Default Logic, originally pre- [Schaub 1992], and approaches to pri-

sented in Reiter [1980], provides formal oritization [Brewka 1994]. In Section 7

methods to support this kind of reason- we briefly discuss some further default

ing. logics, namely Cumulative Default

Default Logic is perhaps the most Logic [Brewka 1991], Rational

prominent method for nonmonotonic [Mikitiuk and Truszczynski 1995],

reasoning, basically because of the sim- Disjunctive Default Logic [Gelfond et al.

plicity of the notion of a default, and 1991], and weak extensions [Marek and

because defaults prevail in many appli- Truszczynski 1993].

cation areas. However, there exist sev- No prior knowledge of Default Logic is

eral alternative design decisions which required since this is a tutorial paper.

have led to variations of the initial idea; However, we assume that the reader is

ACM Computing Surveys, Vol. 31, No. 3, September 1999Ø

Ø

Ø

Ø

Ø

A Tutorial on Default Logics • 339

familiar with notation and the basic The same example could have been

concepts of classical logic. represented by the default

2. DEFAULT LOGIC football : takesPlace

,

takesPlace

2.1 The Notion of a Default

A rule used by football organizers in together with the classical rule snow

Germany might be: “A football game

3 takesPlace. In case we know snow

shall take place, unless there is snow in

then we can deduce takesPlace in clas-the stadium.” This rule of thumb is rep-

sical logic, therefore we cannot assumeresented by the default

takesPlace, as required by the default.

In this representation, the default saysfootball : snow

. “Football matches usually takes place,”

takesPlace

and exceptions to this rule are repre-

sented by classical rules such as the

The interpretation of the default is as

above one.follows: If there is no information that

Defaults can be used to model proto-there will be snow in the stadium, it is

typical reasoning, which means that

reasonable to assume snow and con-

most instances of a concept have some

clude that the game will take place (so

property. One example is the statement

preparations can proceed). But if there

“Typically, children have (living) par-is a heavy snowfall during the night

ents” which may be expressed by thebefore the game is scheduled, then this

defaultassumption can no longer be made. Now

we have definite information that there

child~X! : hasParents~X!

is snow, so we cannot assume snow, .

therefore the default cannot be applied. hasParents~X!

In this case we need to refrain from the

previous conclusion (the game will take A further form of default reasoning is

place), so the reasoning is nonmono- no-risk reasoning. It concerns situations

tonic. where we draw a conclusion even if it is

Before proceeding with more exam- not the most probable, because another

ples, let us first explain why classical decision could lead to a disaster. Per-

logic is not appropriate to model this haps the best example is the following

situation. Of course, we could use the main principle of justice in the Western

rule cultures: “In the absence of evidence to

the contrary assume that the accused is

football ÙØ snow3 takesPlace. innocent.” In default form:

The problem with this rule is that we accused~X! : innocent~X!

have to definitively establish that there .

innocent~X!will be no snow in the stadium before

applying the rule. But that would mean

Defaults naturally occur in many ap-that no game could be scheduled in the

plication domains. Let us give an exam-winter, which would create a revolution

ple from legal reasoning. According toin Germany! It is important to under-

German law, a foreigner is usually ex-stand the difference between having to

pelled if they have committed a crime.know that it will not snow, and being

able to assume that it will snow. De- One of the exceptions to this rule con-

faults support the drawing of conclu- cerns political refugees. This informa-

sions based upon assumptions. tion is expressed by the default

ACM Computing Surveys, Vol. 31, No. 3, September 1999Ø

Ø

Ù

Ø

Ø

Ø

340 • G. Antoniou

ton [1987b]; Lukaszewicz [1990]; andcriminal~X! foreigner~X! : expel~X!

Poole [1994].

expel~X!

2.2 The Syntax of Default Logic

in combination with the rule

A default theory T is a pair ~W, D!

politicalRefugee~X!3 expel~X!. consisting of a set W of predicate logic

formulae (called the facts or axioms of

Hierarchies with exceptions are com-

T) and a countable set D of defaults. A

monly used in biology. Here is a stan-

default d has the formdard example:

Typically, molluscs are shell-bearers.

w : c ,...,c1 nCephalopods are molluscs. are not

x

It is represented by the default

where w, c ,...,c , x are closed1 n

mollusc~X! : shellBearer~X! predicate logic formulae, and n . 0.

The formula w is called the prerequisite,shellBearer~X!

c ,...,c the justifications, and x the1 n

together with the rule consequent of d. Sometimes w is denoted

by pre~d!, $c ,...,c % by just~d!, and1 n

cephalopod~X!3 mollusc~X!

x by cons~d!. For a set D of defaults,

cons~D! denotes the set of consequentsÙØ shellBearer~X!.

of the defaults in D. A default is called

normal iff it has the form w : c c.Defaults can be used naturally to model /

One point that needs some discussionthe Closed World Assumption [Reiter

is the requirement that the formulae in1978], which is used in database theory,

a default be ground. This implies thatalgebraic specification, and logic pro-

gramming. According to this assump-

bird~X! : flies~X!tion, an application domain is described

by certain axioms (in form of relational

flies~X!

facts, equations, rules, etc.) with the

following understanding: a ground fact is not a default according to the defini-

(that is, a nonparameterized statement tion above. Let us call such rules of

about single objects) is taken to be false inference open defaults. An open default

in the problem domain if it does not is interpreted as a default schema,

follow from the axioms. The closed meaning that it represents a set of de-

world assumption has the simple de- faults (this set may be infinite).

fault representation A default schema looks like a default,

the only difference being that w, c ,1true : w

..., c , x are arbitrary predicate logicn

w formulae (i.e., they may contain free

variables). A default schema defines a

for each ground atom w. The explana- set of defaults, namely

tion of the default is: if it is consistent

ws : c s,...,c sto assume w (which is equivalent to 1 n

not having a proof for w) then conclude

xs

w.

Further examples of defaults can be for all ground substitutions s that as-

found in, say, Besnard [1989]; Ethering- sign values to all free variables occur-

ACM Computing Surveys, Vol. 31, No. 3, September 1999Ø

Ø

Ø

Ø

Ø

Ø

Ù

A Tutorial on Default Logics • 341

ring in the schema. That means free T 5 ~W, D! with W 5 $green,

variables are interpreted as being uni-

aaaMember% and D 5 $d , d % with1 2versally quantified over the whole de-

fault schema. Given a default schema

green : likesCars

d 5 ,1

likesCarsbird~X! : flies~X!

flies~X!

aaaMember : likesCars

d 5 .2

and the facts bird~tweety! and likesCars

bird~sam!, the default theory repre-

sented is ~$bird~tweety!, bird~sam!%, If consistency of the justifications was

tested against the set of facts, then both

$bird~tweety! : flies~!/flies~tweety!,

defaults could be subsequently applied.bird~sam! : flies~sam!/flies~sam!%!.

But then we would conclude both

likesCars and likesCars, which is a2.3 Informal Discussion of the Semantics

contradiction. It is unintuitive to let the

Given a default w : c ,...,c x, its

/1 n application of default rules lead to an

informal meaning is the following: inconsistency, even if they contradict

each other. Instead, if we applied the

If w is known, and if it is consistent to

first default, and then checked applica-

assume c ,...,c , then conclude x.1 n tion of the second with respect to the

current knowledge collected so far, theIn order to formalize this interpretation

second default would be blocked: from

we must say in which context w should

the application of the first default we

be known, and with what c ,...,c1 n know likesCars, so it is not consis-

should be consistent. A first guess

tent to assume likesCars. After thesewould be the set of facts, but this turns

examples, here is the formal definition:out to be inappropriate. Consider the

default schema

d 5 w : c ,...,c x is applicable

/1 n

friend~X, Y! friend~Y, Z! : friend~X, Z! to a deductively closed set of formulae

E iff w [ E and c [y E,..., c1 nfriend~X, Z!

[y E.

which says “Usually my friends’ friends

are also my friends”. Given the infor- The example of Greens and AAA mem-

mation friend~tom, bob!, friend~bob, bers indicates that there can be several

competing current knowledge basessally! and friend~sally, tina!, we would

which may be inconsistent with one an-like to conclude friend~tom,

other. The semantics of Default Logic

tina!. But this is only possible if we

will be given in terms of extensions that

apply the appropriate instance of the

will be defined as the current knowl-

default schema to friend~sally, tina! edge bases satisfying some conditions.

and friend~tom,! sally}. The latter for- Intuitively, extensions represent possi-

mula stems from a previous application ble world views which are based on the

1

of the default schema. If we did not given default theories; they seek to ex-

admit this intermediate step and used tend the set of known facts with “rea-

the original facts only, then we could sonable” conjectures based on the avail-

not get the expected result. able defaults. The formal definition will

Another example is the default theory be given in the next subsection. Here we

just collect some desirable properties of

1With other instantiations, of course. extensions.

ACM Computing Surveys, Vol. 31, No. 3, September 1999Ø

Ø

Ø

Ø

Ø

Ø

Ø

Ø

Ø

342 • G. Antoniou

2.4 An Operational Definition of—An extension E should include the set

Extensions

W of facts since W contains the cer-

tain information available: W # E. For a given default theory T 5 ~W, D!

letP5~d , d ,...! be a finite or infi-0 1

—An extension E should be deductively nite sequence of defaults from D with-

closed because we do not want to pre- out multiple occurrences. Think of P as

vent classical logical reasoning. Actu- a possible order in which we apply some

ally, we want to draw more conclu- defaults from D. Of course, we don’t

sions, and that is why we apply want to apply a default more than once

default rules in addition. Formally: E within such a reasoning chain because

no additional information would be

5 Th~E!, where Th denotes the de-

gained by doing so. We denote the ini-ductive closure.

tial segment of P of length k by P@k#,

— provided the length of P is at least kAn extension E should be closed un-

(from now on, this assumption is always

der the application of defaults in D

made when referring to P@k#). With

(formally: if w : c ,...,c x [ D,

/1 n

each such sequence P we associate two

w [ E and c [y E,..., c [y E1 n

sets of first-order formulae, In~P! and

then x [ E). That is, we do not stop

Out~P!:

applying defaults until we are forced

to. The explanation is that there is no —In~P! is Th~W ł $cons~d!?d occurs

reason to stop at some particular

in P}. So, In~P! collects the informa-

stage if more defaults might be ap-

tion gained by the application of the

plied; extensions are maximal possi-

defaults in P and represents the cur-ble world views.

rent knowledge base after the defaults

in P have been applied.

These properties are certainly insuffi- —Out~P! 5 $ c?c [ just~d! for some

cient because they do not include any

d occurring in P}. So, Out~P! collects

“upper bound,” that is, they don’t pro- formulae that should not turn out to

vide any information about which for- be true, i.e., that should not become

mulae should be excluded from an ex- part of the current knowledge base

tension. So we should require that an even after subsequent application of

extension E be minimal with respect to other defaults.

these properties. Unfortunately, this re-

Let us give a simple example. Considerquirement is still insufficient. To see

the default theory T 5 ~W, D! with Wthis, consider the default theory T 5

5 $a% and D containing the following

~W, D! with W 5 $aussie% and D 5

defaults:

$aussie : drinksBeer/drinksBeer%.

Let E 5 Th~$aussie,%!. a : b b : c

d 5 , d 5 .1 2It is easily checked that E is minimal b c

with the three properties mentioned

above, but it would be highly unintui-

For P5~d ! we have In~P! 5 Th~$a,1tive to accept it as an extension, since

b%! and Out~P! 5 $b%. For P5~d ,2that would support the following argu-

d ! we have In~P! 5 Th~$a, c, b%!ment: “If Aussies usually drink Beer 1

and if somebody is an Aussie, then as- and Out~P! 5 $ c, b%.

sume that she does not drink Beer.” Up to now we have not assured that

ACM Computing Surveys, Vol. 31, No. 3, September 1999Ø

Ø

Ø

Ø

A Tutorial on Default Logics • 343

the defaults in P can be applied in the

order given. In the example above, ~d ,2

d ! cannot be applied in this order (ap-1

plied according to the definition in the

previous subsection). To be more spe-

cific, d cannot be applied, since b [y2

In~~!! 5 Th~W! 5 Th~$a%! which is

the current knowledge before we at-

tempt to apply d . On the other hand,2 Figure 1. A process

there is no problem with P5~d !;in tree.1

this case we say that P is a process of T.

Here is the formal definition:

Th~$a, b%! is an extension of T, in fact—

P is called a process of T iff d isk its single extension.

applicable to In~P@k#!, for every k

Definition 1. A set of formulae E issuch that d occurs in P.k

an extension of the default theory T iff

there is some closed and successful pro-Given a process P of T we define the

following: cess P of T such that E 5 In~P!.

In examples, it is often useful to ar-

—

P is successful iff In~P! ø Out~P! range all possible processes in a canoni-

5 À, otherwise it is failed. cal manner within a tree, called the

process tree of the given default theory

—

P is closed iff every d [ D that is T. The nodes of the tree are labeled

applicable to In~P! already occurs in with two sets of formulae, an In-set (to

P. Closed processes correspond to the the left of the node) and an Out-set (to

desired property of an extension E the right of the node). The edges corre-

being closed under application of de- spond to default applications, and are

faults in D. labeled with the default that is being

applied. The paths of the process tree

Consider the default theory T 5 ~W, starting at the root correspond to pro-

D! with W 5 $a% and D containing the cesses of T.

following defaults

2.5 Some Examples

a : b true : c

d 5 , d 5 .1 2 Let T 5 ~W, D! with W 5 À and D 5

d b

$true : a/ a%. The process tree in Fig-

ure 1 shows that T has no extensions.

P 5 ~d ! is successful but not closed1 1

Indeed, the default may be applied be-

since d may be applied to In~P ! 52 1 cause there is nothing preventing us

Th~$a, d%!. P 5 ~d , d ! is closed but2 1 2 from assuming a. But when the default

not successful: both In~P ! 5 Th~$a,2 is applied, the negation of a is added to

d, b%! and Out~P ! 5 $b, c% contain2 the current knowledge base, so the de-

b. On the other hand, P 5 ~d ! is a fault invalidates its own application be-3 2

closed and successful process of T. cause both the In and the Out-set con-

According to the following definition, tain a. This example demonstrates

which was first introduced in Antoniou that there need not always be an exten-

and Sperschneider [1994], In~P ! 5 sion of a default theory.3

ACM Computing Surveys, Vol. 31, No. 3, September 1999Ø

Ø

Ø

Ø

Ø

Ø

Ø

344 • G. Antoniou

Figure 2. A process tree.

2.6 Reiter’s Original Definition ofLet T 5 ~W, D! be the default theory

Extensions

with W 5 À and D 5 $d , d % with1 2

In this subsection we present Reiter’s

true : p true : q original definition of extensions [Reiter

d 5 , d 5 .1 2 1980]. In 2.3 we briefly ex-q r

plained that the most difficult problem

in describing the meaning of a default is

The process tree of T is found in Figure

to determine the appropriate set with

2 and shows that T has exactly one which the justifications of the defaults

extension, namely Th~$ q%!. The right must be consistent. The approach

path of the tree shows an example adopted by Reiter is to use some theory

where application of a default destroys beforehand. That is, choose a

the applicability of a previous default: which plays the role of a context or belief

set and always check consistency

d can be applied after d , but then q1 2

against this context. Let us formalizebecomes part of the In-set, whilst it is

this notion:

also included in the Out-set (as the

negation of the justification of d ).2 —A default d 5 w : c ,...,c x is

/1 n

Let T 5 ~W, D! with W 5 $green, applicable to a deductively closed set

aaaMember% and D 5 $d , d % with1 2 of formulae F with respect to belief set

E (the aforementioned context) iff w

green : likesCars

d 5 , [ F, and c [y E,..., c [y E1 1 n

likesCars

(that is, each c is consistent with E).i

aaaMember : likesCars Note that the concept “ d is applicable to

d 5 .2

likesCars E” used so far is a special case where

E 5 F. The next question that arises is

The process tree in Figure 3 shows which context to use. First, note that

that T has exactly two extensions when a belief set E has been estab-

(where g stands for green, a for lished, some formulae will become part

aaaMember, and l for likesCars). of the knowledge base by applying de-

ACM Computing Surveys, Vol. 31, No. 3, September 1999A Tutorial on Default Logics • 345

Figure 3. A process tree.

ous obstacles in understanding the con-faults with respect to E. Therefore, they

cepts of Default Logic and in being ableshould be believed, i.e., be members of

to apply them to concrete cases.E. On the other hand, what would be a

The following theorem shows that Re-justification for a belief if it were not

iter’s extension concept is equivalent toobtained from default application w.r.t.

the definition in subsection 2.4.

E? We require that E contain only for-

mulae that can be derived from the axi- THEOREM 1. Let T 5 ~W, D! be a de-

oms by default application w.r.t. E. fault theory. E is an extension of T (in

Let us now give a formal presentation the sense of definition 2.1) iff E 5

of these ideas. For a set D of defaults,

L ~E!.T

we say that F is closed under D with

We conclude by giving a quasiinduc-respect to belief set E iff, for every de-

tive characterization of extensions, also

fault d in D that is applicable to F with

due to Reiter: Given a default theory T

respect to belief set E, its consequent x

5 ~W, D!, we say that E has a quasi-

is also contained in F.

inductive definition in T iff E 5 ł E ,iiGiven a default theory T 5 ~W, D!

where E 5 Th~W! and E 5 Th~Eand a set of formulae E, let L ~E! be 0 i11 iT

the least set of that contains

ł $cons~d!%d [ D! is applicable to Ei

W, is closed under logical conclusion w.r.t. belief set E}.

(i.e., first-order deduction), and closed

THEOREM 2. E is an extension of T iff

under D with respect to E. Informally

E has a quasiinductive definition in T.speaking, L ~E! is the set of formulaeT

that are sanctioned by the default the- This characterization replaces the

ory T with respect to the belief set E.

L -operator by a construction, both ofT

Now, according to Reiter’s definition,

them using the set E as context or belief

E is an extension of T iff E 5L~E!.T set. Given a set of formulae E, this

This fixpoint definition says that E is characterization is intuitively appeal-

an extension iff by deciding to use E as ing. But notice that still it is necessary

a belief set, exactly the formulae in E to first guess E before checking whether

will be obtained from default applica- it is an extension. In this sense, the

tion. But please note the difficulty in characterization is not as easy to apply

applying this definition: we have to as the process model from subsection

guess E and subsequently check for the 2.4.

fulfillment of the fixpoint equation. The relationship of processes to the

Having to guess is one of the most seri- quasiinductive definition is that the tra-

ACM Computing Surveys, Vol. 31, No. 3, September 1999Ø

Ø

346 • G. Antoniou

versal of the process tree operational- heterogeneous information sources,

izes the idea of guessing. More formally: where it is not easy to identify which

if a branch of the process tree leads to a source is responsible for the deficiency,

or where the single pieces of informa-closed and successful process P, then

tion are meaningful, but lead to prob-the quasiinductive construction using

lems when put together.

In~P! as a belief set yields the same

A more technical argument in favor of

result. But some branches of the process

the second view is the concept of semi-

tree can lead to failed processes; this is

monotonicity. Default Logic is a method

the price we have to pay if we wish to

for performing nonmonotonic reasoning,

avoid guessing.

so we cannot expect it to be monotonic

when new knowledge is added to the set

3. PROPERTIES OF DEFAULT LOGIC of facts. However, we might expect that

the addition of new defaults would yield

In this section we discuss some proper- 2more, and not less information. For-

ties of Default Logic. Some of these

mally, semi-monotonicity means the fol-

properties can be interpreted as defi-

lowing:

ciencies, or they highlight some of Reit-

er’s original “design decisions” and show Let T 5 ~W, D! and T95~W, D9! be

alternative ideas that could be followed

default theories such that D # D9.

instead. In this sense, the discussion in

Then for every extension E of T therethis section motivates alternative ap-

is an extension E9 of T9 such that Eproaches that will be presented in sub-

sequent sections. One point that should # E9.

be stressed is that there is not a “cor-

Default Logic violates this property. For

rect” default logic approach, but rather

example, T 5 ~À, $true : p/p%! has thethe most appropriate for the concrete

problem at hand. Different intuitions single extension E 5 Th~$p%!, but T9

lead to different approaches that may

5 ~À, $true : p/p, true : q/ q%! has no

work better for some applications and extension. So nonexistence of extensions

worse for others. leads to the violation of semi-monotonic-

ity. Even though the concept of semi-

monotonicity is not equivalent to the3.1 Existence of Extensions

existence of extensions, these two prop-

We saw that a default theory may not erties usually come together (for a more

have any extensions. Is this a shortcom- formal support of this claim see Anto-

ing of Default Logic? One might hold niou et al. [1996]).

the view that if the default theory in- If we adopt the view that the possible

nonexistence of extensions is a problem,cludes “nonsense” (for example true :

then there are two alternative solutions.p p), then the logic should indeed be

/

The first one consists in restricting at-allowed to provide no answer. According

tention to those classes of default theo-to this view, it is up to the user to

ries for which the existence of exten-provide meaningful information in the

sions is guaranteed. In his classicalform of facts and defaults;

paper [Reiter 1980], Reiter alreadyafter all, if a program contains an error,

showed that if all defaults in a theory Twe don’t blame the programming lan-

guage. are normal (in which case T is called a

The opposite view regards nonexist- normal default theory), then T has at

ence of extensions as a drawback, and

would prefer a more “fault-tolerant” logic;

one which works even if some pieces of 2Some researchers would disagree with this view

information are deficient. This view- and regard semi-monotonicity as not desirable;

point is supported by the trend towards see, for example, Brewka [1991].

ACM Computing Surveys, Vol. 31, No. 3, September 1999

Access to the YouScribe library is required to read this work in full.

Discover the services we offer to suit all your requirements!

Our offers

Read an excerpt

Sorry, but you appear to have insufficient credit. To subscribe, please top up your account.

© 2010-2020 YouScribe