A 5" a4- , fl. , «.(ns’m 4 O ' I I. ’3‘”... x i 29365:; .- A -_ A. ‘ “egzewt J.— _ I- ~.,-. . .n. 5‘31"”- 4nf~ ‘. "’4‘ ‘Jvz. . V; o ‘ ‘ aicfis * i“ WA‘rw; " 4'“ - “ W: ‘ “7'11 .m‘nV , , ifii This is to certify that the dissertation entitled REASONING WITH CONTRADICTORY DEDUCTIVE DATABASES presented by ANASTAS IA ANALYTI has been accepted towards fulfillment of the requirements for PhD COWUTER SCIENCE degree in L": \E‘o’acmawv: \Q Major professor Date MS U is an Affirmative Action/Equal Opportunity Institution 0-12771 » «iiiiiiiiiiiiiw LIBRARY Michigan State University PLACEfll-IETURNBOXto tomovo thloochockommmywrocad. TO DA lDFINESrotumonor botmdoto duo. DATE DUE DATE DUE DATE DUE MSU IoAn Afflmofivo Action/Emu Oppomnlty Inothdlon mm: REASONING WITH CONTRADICTORY DEDUCTIVE DATABASES By Anastasia Analyti A DISSERTATION Submitted to Michigan State University in partial firlfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Computer Science 1 994 ABSTRACT REASONING WITH CONTRADICTORY DEDUCTIVE DATABASES By Anastasia Analyti Deductive databases have become a dominant field of research in recent years because they provide (i) an expressive environment for data modelling, (ii) a single, declarative language for expressing queries, constraints, views, and programs, and (iii) a clear separation of declarative and procedural concepts. A deductive database consists of two parts: a set of known facts, and a set of rules fi’om which new facts can be derived. Consistency of derived facts is not a realistic assumption in many applications. In the presence of contradiction, classical logic fails to give any semantics to the deductive database. Thus, even a single erroneous datum could destroy all meaningful information. The goal of this research is to derive useful information fiom a set of contradictory rules. In the investigated framework, both negation by default and classical negation are supported. Rules are equipped with a partial order expressing their relative reliability in case of conflict. In this thesis, we propose the reliable semantics and contradiction-free semantics for contradictory deductive databases. In the proposed semantics, a rule ordering based on reliability is used to choose between conflicting rules. When no choice is possible, the conflicting rules are considered unreliable and their conclusions are blocked. Conclusions from rules that do not contribute to the contradictions are considered reliable and they are used for the derivation of new information. We give equivalent fixpoint and model theoretic characterizations of the proposed semantics. For the contradiction-free semantics we present an equivalent procedural characterization for computing answers to queries. Both skeptical and credulous types of reasoning are considered. Some of the advantages of the proposed semantics are: (i) they cover a broader domain of logic programs than those semantics proposed earlier, (ii) they are well-defined for every contradictory program in this broader domain, (iii) they extend several semantics proposed earlier, and (iv) they can be computed in polynomial time with respect to the size of the program P when the Herbrand Base of P is finite. A more general framework is presented where rules are encapsulated into modules. The prospect of contradiction is even stronger when information is distributed in a set of modules. The code of a module is usually hidden from other modules. Thus, modules export their results while they hide the way these results are computed. A partial order expresses the relative reliability of conclusions drawn by these modules. The semantics for this extended framework is called modular reliable semantics. We present a fixpoint and model theoretic characterization of the modular reliable semantics. This framework can be used to model multi-agent systems where the knowledge of several experts is represented in a single system. An application of the reliable semantics to deductive object-oriented databases is also described. In deductive object-oriented databases, rule prioritization can be used (i) to express the fact that specific rules are more reliable than general ones, (ii) to give priorities to inherited rules that are in conflict as a result of multiple inheritance and (iii) to give priorities to class rules that are in conflict as a result of multiple specializations of the same object. To my parents ACKNOWLEDGEMENTS I would like to thank my advisor Dr. Sakti Pramanik for all his support in my academic and personal life. He helped me build a strong background in the database area. He taught me how to do research and attack problems. He helped me financially in all possible ways and gave me emotional support when I most nwded. I would like to thank Dr. Herman Hughes, Dr. William Punch, 111, Dr. Gerald Ludden, and Dr. Jacob Plotkin for serving as my committee members and helping me in identifying some of the important issues investigated in this thesis. I would also like to express my appreciation to the Computer Science Department and College of Engineering for their financial support. Many thanks go to Vasu Vuppala and Walid Tout for answering my numerous Unix-related questions. My friends Argyrios Geralds, Michael Tomaritis, Mingxia Man, Divesh Srivastava, and Anastassios Petropoulos have been a powerful source of support. Finally, I would like to thank my parents for their encouragement in achieving my academic goals. ii TABLE OF CONTENTS LIST OF FIGURES v 1 INTRODUCTION 1 l. 1 Problem Description . l 1.2 Overview of Semantics for Logic programs 2 1.3 Our Approaches for Avoiding Contradictions 9 1.4 Dissertation Outline . . . l4 2 RELIABLE SEMANTICS FOR EXTENDED LOGIC PROGRAMS WITH RULE PRIORITIZATION 17 2.1 Introduction . . 17 2. 2 r-models for Extended Programs with Rule Prioritization. 18 2. 3 Reliable Semantics . . . 28 2.3.1 Reliable Model 28 2.3.2 Stable r-models . 34 2. 3. 3 Diagnosis Example . 39 2. 4 Related Work. . . 41 2. 4. l Three-Valued Stable Model Semantics . 41 2. 4.2 Answer Set Semantics . . 42 2 ..4 3 Extended Well-Founded Semantics 43 2.4.4 Relevant Expansion 44 2.4.5 Conservative Vivid Logic 44 2.4.6 Predicate Logic Extensions 45 2.4.7 Ordered Logic . 46 2.4.8 Default Logic . 50 2.5 Conclusions 53 3 MODULAR RELIABLE SEMANTICS FOR MODULAR LOGIC PROGRAMS WITH RESULT PRIORITIZATION 55 3.1 Introduction . . . 55 3 .2 Informal Presentation and Intuitions . . 57 3. 3 m-models for Prioritized Modular Logic programs . 60 3 .4 Modular Reliable Semantics for Prioritized Modular Logic Programs 68 3.4.1 Reliable m-model . . . . 68 3. 4. 2 Stable m-models . 74 3 .5 Modular Reliable Semantics for Prioritized Extended Logic Programs 78 3 ..5 1 Definitions . . 79 3.5.2 Relationship with the Modular Reliable Semantics of Modular Logic Programs. 81 3 .6 Related Work. . . 84 3.6.1 Combining Multiple Deductive Databases . . 84 3. 6.2 A Distributed Assumption Truth Maintenance System. 86 TABLE OF CONTENTS LIST OF FIGURES v 1 INTRODUCTION 1 l. 1 Problem Description . l 1.2 Overview of Semantics for Logic programs 2 1.3 Our Approaches for Avoiding Contradictions 9 1.4 Dissertation Outline . . . l4 2 RELIABLE SEMANTICS FOR EXTENDED LOGIC PROGRAMS WITH RULE PRIORITIZATION 17 2.1 Introduction . . . . . . . l7 2. 2 r—models for Extended Programs with Rule Prioritization. . . . . . l8 2. 3 Reliable Semantics . . . . . . . . . . . . . 28 2.3.1 Reliable Model . . . . . . . . . . . . . 28 2.3.2 Stable r-models . . . . . . . . . . . . . 34 2. 3. 3 Diagnosis Example . . . . . . . . . . . . . 39 2. 4 Related Work. . . . . . . . . . . 41 2.4.1 Three-Valued Stable Model semantics . . . . . . . . . 41 2. 4. 2 Answer Set Semantics . . . . . . . . . . . 42 2. 4. 3 Extended Well-Founded Semantics . . . . . . . . . 43 2.4.4 Relevant Expansion . . . . . . . . . . . . 44 2.4.5 Conservative Vivid Logic . . . . . . . . . . . 44 2.4.6 Predicate Logic Extensions . . . . . . . . . . . 45 2.4.7 Ordered Logic . . . . . . . . . . . . . . 46 2.4.8 Default Logic . . . . . . . . . . . . . . 50 2.5 Conclusions . . . . . . . . . . . . . . . 53 3 MODULAR RELIABLE SEMANTICS FOR MODULAR LOGIC PROGRAMS WITH RESULT PRIORITIZATION 55 3.1 Introduction . . . . . . . . . . . . 55 3. 2 Informal Presentation and Intuitions . . . . . . . . . 57 3. 3 m-models for Prioritized Modular Logic programs . . . . 60 3. 4 Modular Reliable Semantics for Prioritized Modular Logic Programs . . . 68 3 ..4 l Reliable m-model . . . . . . . . . 68 3.4.2 Stable m-models . . . . . 74 3. 5 Modular Reliable Semantics for Prioritized Extended Logic Programs . . . 78 3.5.1 Definitions . . 79 3.5.2 Relationship with the Modular Reliable Semantics of Modular Logic Programs. 81 3. 6 Related Work. . . 84 3.6.1 Combining Multiple Deductive Databases . . . . . . . 84 3. 6. 2 A Distributed Assumption Truth Maintenance System. . . . . . 86 3.7Conclusions...............87 4 CONT RADICT ION-F REE SEMANTICS FOR EXTENDED LOGIC PROGRAMS WITH RULE PRIORITIZATION 89 4.1 Introduction. . . . . . . . . . 89 4. 2 c-models for Prioritized Extended Programs . . . . . . . . 90 4. 3 Contradiction-Free Semantics . . . . . . . . . . . 94 4. 4 Related Work. . . . . . . . . . . . 98 4.4.1 Semantics Covered in Section 2.4.. . . . . . . 98 4. 4. 2 Semantics Following the Contrapositive Rule Approach . . . . . 101 4 4. 3 Doyle's Truth Maintenance System . . . . . . . . . 102 4.5 Procedural Semantics . . . . . . . . . . . . . 106 4.6 Conclusions . . . . . . . . . . . . . . . 112 5 RELIABLE OBJECT LOGIC 115 5.1 Introduction . . . . . . . . . . . . 115 5. 2 Reliable Object Logic Programs. . . . . . . . . . . 117 5. 3 Reliable Semantics for ROL Programs . . . . . . . . . 121 5.4 Conclusions . . . . . . . . . . . . . . . 126 6 CONCLUSIONS AND FUTURE RESEARCH 127 A PROOFS OF SECTION 4.3 133 B PROPOSITIONAL PROOF THEORY AND PROLOG META-INTERPRETERS 139 8.1 Contradiction-Free Semantics . . . . . . . . . . . 139 8.2 Reliable Semantics . . . . . . . . . . . . . 142 BIBLIOGRAPHY 146 iv LIST OF FIGURES 2.1 A digital circuit . . . . . . . . . . . . . . 39 3.1 DNA fragments . . . . . . . . . . . . . . 62 5.1 A class hierarchy . . . . . . . . . . . . . . 119 CHAPTER 1 INTRODUCTION 1.1 Problem Description A deductive database is a set of sentences in a knowledge representation language. The knowledge representation language that we consider here is logic programming. Logic programs represent information about a problem in temrs of rules. The idea that logic can be used as a programming language was introduced by Colmerauer and Kowalski [41]. The semantics of a logic program specifies what is true or false and can be defined declaratively or procedurally. The declarative characterization of a logic program is the specification of its "meaning" in terms of a fixpoint of an operator (fixpoint semantics) or in terms of a particular set of interpretations satisfying certain properties (model theoretic semantics). The procedural characterization of a logic program is given through a query answering algorithm that receives as input a specific query and retums its truth value. Classical logic has been successful only in representing very precise reasoning such as that found in mathematics. However, human reasoning is often based on conflicting evidence and on assumptions which are not always valid. When a logic program is contradictory, instead of discarding the whole program, we would like to separate the reliable from the unreliable part of the information. This way, useful conclusions can be derived from the reliable information. The goal of this work is to define semantics for logic programs that may be contradictory. The semantics should extend well-known semantics for non-contradictory logic programs. We consider rules to be defaults. Rule prioritization can be viewed as a tool to specify confidence information about these defaults. Some of the reasons for rule prioritization are: 2 0 Dijkrence in the reliability of sources. It is possible that a number of sources provide infomration about a particular topic. If the sources contradict, we wish to use ordering to resolve conflicts. o The dominance of specific over general information. Object-oriented programming is an example where this principle is employed. 0 Regulation. Regulation can indicate the priority of different conflicting directives. For example, university laws require that foreign students pay out-of-state tuition and TAs pay in-state tuition. However, if a student is both foreign and TA, the directives for TAs are given higher priority than the directives for foreign students. The prospect of contradiction is even stronger when information is distributed in a set of modules. The code of a module is usually hidden from other modules. Thus, modules export their results while they hide the way these results are computed. When exported results are in conflict, prioritization of results can express higher confidence in some results over others. 1.2 Overview of Semantics for Logic programs A normal logic program P consists of a finite set of clauses of the form: At—L],...,L,,, where A is an atom and ViS n, L,- is a literal, i.e., an atom or its negation. The atom on the left hand side of a rule is called the head of the rule and is denoted by Head,. The expression on the right hand side of the rule is called the body of the rule and is denoted by Body,. The Herbrand Universe of P is the set of all ground (variable-fies) temrs which can be formed by using the constant and function symbols appearing in P. The Herbrand Base of P ([1812) is the set of all ground atoms which can be formed by using the predicates appearing in P with the terms in the Herbrand Universe of P. A 2-valued model of a program P evaluates each literal in HBP as true (value 1) or false (value 0). A 2-valued model M is represented as a subset of HBP where atoms in M are true and atoms not in M are false. In contrast, a 3-valued model of P evaluates each literal in HBP as true (value 1), false (value 0) or unknown (value 1/2) and is represented as a subset of HBP U ~HBP. For any 3-valued model M, there is no atom A St. AeM and ~AeM. IfAeM then A is true, if 3 ~AeM then A is false, and if neither AeM nor ~AeM then A is unknown. Let M be a 2-valued or 3-valued model of P. The truth value of a set of literals S w.r.t. M is defined as the least truth value of the literals in S. Let M(S) denote the truth value of S w.r.t. M, where S is a literal or a set of literals. Then, M(Head,)2M(Body,.), for every rule r in P. Initial work on logic programming was only concerned with logic programs with no negation (Horn logic programs). Inspired by SL-resolution [40] (linear resolution with selection function), ' Hill [33] developed a linear resolution procedure, called SLD-resolution (SL-resolution for definite programs). A goal in an SLD-resolution is of the form (—Al ..... A", where A,- are atoms. An SLD- refutation ofgoal G] = (-Al.....An is a sequence ofgoals 01,...,Gnv s.t. Gnv = (— and Vi. R p is a finite set of rules r: Lot— L1,...,Lm,~Lm+1,...,~L,,, where r is a label and L,- are classical literals. Every rule r has a corresponding set S, cBody,, called the preliminary suspect set of r. ICp is a finite set of constraints .l.<—L1,...,Lk, where L; are classical literals. The precise meaning of S, will be given in the definitions. Intuitively, when a constraint .Lt—Ll....,Lk is violated, the rules used in the last step of the derivation of L,- are considered "suspect." Ifa rule r is "suspect" for a constraint violation then the rules and CWAs used in the last step of the derivation of literals in S, are also "suspect." 19 The values of S, depend on the reasons for a constraint violation. There are two basic views on the reasons for the violation of a constraint J.<—L1,..,Lk: (v1) rules used in the last step of the derivation of L,- are incomplete1 or (v2) CWAs and/or rules used in same step of the derivation of L; are unreliable. According to the first view (v1), the skeptical meaning of the program P' ={rlz a<—. r2: b<—. r3:p(—a. r4: “pt—b} is {a, b}. Rules r] and r2 are not used in the last step ofthe derivation of p, -'p and thus according to (v1), they are reliable. On the contrary, rules r3 and r4 are used in the last step of the derivation of p, “p and thus they are considered incomplete, i.e., r3 should be pt—a,~b or r4 should be "pt—bra. Consequently, the literals a, b are evaluated as true whereas both p and “'p are undefined. View (v1) is implied by ordered logic [24, 43] and vivid logic [77] and becomes explicit in our framework when S,={} V rule r. For example, if S,,={}, Vis4 then rules r3 and r4 are "suspect" for the violation of .Lt—p,‘*p. However, rules r1 and r2 are not "suspect" because the literals a and b do not belong to S,3 or S”. According to the second view (v2), which is more conservative than (v1), the skeptical meaning of P' is {}. This is because all rules in P' are used in the derivation of p, "p and thus all rules in P’ are considered unreliable. View (v2) becomes explicit in our framework when S,=Body,, V rule r. For example, if Sn =Body,, , ViS4 then not only nrles r3, r4 but also r1, r2 are ”suspect” for the constraint violation. Other views corresponding to S, ${} and S, tit-Body, for a rule r are also possible. For exarnple, consider the program P'={r1: a(—. r2: b(—. r3: “p<—. r4: pt—a,b.}. If S,4={a} then rule r, is "suspect" for the violation of .Lt—prp and rule r2 is not. Consequently, the skeptical meaning of P' is {b}. Similarly, if S,4={b} then the skeptical meaning of P' is {a}. The relation : Rp={ I‘ IfAnn is a foreign student (resp. teaching assistant) then she needs 12 (resp. 6) credits I"I r1 : need_credits(ann, 12)<—foreign_stud(ann). r2: need_credits(ann,6)e—TA(ann). r3: TA(ann). r4: foreign_stud(ann). where S,,={ }, V154}, ICp={ ic: .l.(—need_credits(ann,6), need_credits(ann,12). } and r1: Rp={ r1: loaded(tl)<—loaded(t0). rn: loaded(t,,)<—loaded(tn_1). r0: Ioaded(t0). rmlz aloaded(tn). where S,,.={ }, ViSn+l } , 1Cp=BCp and ’i< r0 and "i< 'n+lt Vie {l,..., n} }. Rules r1,...,rn are instances of the default rule "if a gun is loaded at time t,- tlren it will still be loaded at time ’i+l ." Rules r0 and rm] represent the facts that the gun is loaded at time to and it is found unloaded at time ’n- Note that every classical model of Rp violates the constraint .Lt-loaded(tn),-'loaded(t,,). The rules r0 and rm] are reliable because they have higher priority than r‘,...,r,, and they do not generate any constraint violation. Since S,,,={}, the rules r‘,...,r,,-1 are not ”suspect" for the constraint violation even though they are used in the derivation of loaded(tn). So, rules rl,...,r,,-1 are reliable and the only unreliable rule is rn. This implies that the gun remained loaded until ’n-l' If S,,={loaded(ti-l)}, VISiSn, then all rules r-, j=l,...,n, are "suspect" for the constraint violation because they are used in the derivation of loaded(tj), j=l,...,n. Consequently, all rules r1,...,r,, are unreliable. This implies that the gun was unloaded some time between t1 and tll but we do not know exactly when. Definition 2.2.1 (interpretation): Let P be an EPP. A set l=7U~F is an interpretation of P iff T and F are disjoint subsets of HBp. An interpretation 1 is consistent ifl‘ there is no constraint .L(-—L1,...,Ln in P s.t. Lie T, ViSn. An interpretation I is coherent ifl‘ it satisfies the coherence property. Le F if-rLe T. 22 In interpretation I=7U~F, T contains the classically true literals, ”'7' contains the classically false literals and F contains the literals false by default. When I is a consistent interpretation, there is no L such that Le T and "Le T because this will violate the basic constraint .L(-—L,-'L. The coherence property first appeared in [54] and it expresses the intuition that if a literal is classically false then it is also false by default. Definition 2.2.2 (truth valuation of a literal): A literal L is true (resp. false) w.r.t. an interpretation I iffLeI (resp. ~LeI). A literal that is neither true nor false w.r.t. I, it is undefined w.r.t. I. An interpretation 1 can be seen equivalently as a firnction from the set of ground classical literals to {OJ/2,1}, where 1(L)=l when L is true w.r.t. I, 1(L)=O when L is false w.r.t. I and 1(L)=l/2 when L is undefined w.r.t. 1. Both views of an interpretation, as a set and as a function, will be used in the paper. Note that, I(~L)=l—I(L), for any literal L. If I is a coherent interpretation then 1(L)=l implies I(~L)=0. We define [(0)351 and I(S)=Mmin{I(L)| LeS} where S is a non- empty set of literals. The coherence operator (coh) transforms an interpretation to a coherent one. Definition 2.2.3 (coh operator [54]): Let I=TU~F be an interpretation of an EPP. coh(I) is the coherent interpretation NF, where F=RJ{L| "Le T}. Let I be a set of literals known to be true. In Definitions 2.2.6 and 2.2.8, the concepts of reliable default literal and reliable rule w.r.t. I are defined. These concepts are used in the fixpoint computation of the RS of an EPP. In RS, a default literal ~L is true by C WA only if ~L is a reliable default literal w.r.t. RS and a rule r is used for the derivation of Head,. only if r is a reliable rule w.r.t. RS. The next definition expresses that a rule r should be blocked if *Head, is known to be true. Definition 2.2.4 (blocked rule): Let I be a literal set. A rule r is blocked w.r.t. I ifi‘ "Head,.e I. 23 To decide if a default literal is reliable w.r.t. I, all possible constraint violations should be considered. For this, the set of literals P051 is computed. Intuitively, Posl is the possibly inconsistent well-founded model of R p when rules are blocked as indicated in I and coherence is enforced. Specifically, P031 is the least fixpoint of the monotonic operator PW 1 which resembles the W operator of the well-founded semantics [76]. When P is a normal program, PWQEW. Definition 2.2.5 (possible literal set w.r.t. I): Let P be an EPP and 1,] be sets of literals. The possible literal set w.r.t. 1, Pos 1, is defined as follows: 0 PTLJ(])={L | El rule r: L<—L1,...,Ln in P s.t. r is not blocked w.r.t. I and Lie TUJ, ViSn}. . PT1(J)= utprulam) | a<(n}, where (i) is the first marine ordinal. 0 PF(J) is the greatest set S of classical literals s.t. VLeS, if r is a rule in P s.t. Head,.-"L then 3L'e Body, s.t. L'e S or ~L'eJ}). 0 PW 1(J)=coh(PT1(J)u~PF(J)). - P031 is the least fixpoint of the operator PW 1. A default literal ~K is reliable w.r.t. I if there is no constraint violation caused by Posl that depends on ~K. In other words, ~K is reliable if it is not "suspect" for any constraint violation. If r is a rule with Body, :Posl and a constraint violation depends on Head,. then the constraint violation depends also on all literals in S,. If a constraint violation depends on a default literal ~K then the constraint violation depends also on -'K. Definition 2.2.6 (dependency set w.r.t. I, reliable default literal): Let P be an EPP, L be a literal and I be a set of literals. o The dependency set of L w.r.t. I, Dep1(L), is the least set D(L) such that: - if L is the default literal ~K then {~K} ;D(~K) and D(‘*K)<;D(~K). - if 3 r: Le—L1,...,Ln in P s.t. Body, cPosI then {L}:D(L) and VLie Sr, D(L,);D(L). o A default literal ~K is unreliable w.r.t. I iffB .Le—L1,...,L,, in P s.t. ~Ke Dep1(Li), for an tSn and Lje P051, Vje { l,...,n}-{t}. Otherwise, ~K is reliable w.r.t. I. 24 Note that only the dependency sets of literals in S, are considered in the computation of Dep1(Head,.). This is because even if r is "suspect" for a constraint violation caused by Pos1, the rules and C WAs used in the derivation of Bodyr—S, are not necessarily "suspect" for this constraint violation. Example 2.2.3: Consider the EPP, P=z Rp=(r1:fly. rzzqfly(—~bird. with Sn={~bird} }, ICp=BCp and and P'= be EPPs, where be an EPP and is an r-model of P. Proof: Let M be an r-model of P'. Then, M is a consistent, coherent interpretation of P. If r is a rule in P then r is r-true w.r.t. M in P'. We will show that r is r-true w.r.t. M in P. It is enough to show that if r is unreliable w.r.t. M in P' then r is unreliable w.r.t. M in P. Assume that r is unreliable w.r.t. M in P'. Since : Rp=(r1: q. r2: p(—q. r3: “p. r4: p<—~r. with S,,=Body,,, Vis4}, ICp=BCp and r3 be an EPP. The complexity of computing RMp is 0(ll-IBp|*|Rp|‘max(|ICp|, lHBp|*lECRI), where ECR is the set of equivalence classes of Rp w.r.t. '3- Proof: The following algorithm, RM(program P), returns the reliable model of P. To compute F(l), its complement set is constructed first, as in [76]. RM(EPP program P) { new_1={}; repeat I=new_I; compute Pos[, /" Step I *l for each Le HBp do compute Dep1(L); endfor /‘ Step 2 ‘/ for each m inP do /" Step 3 */ compute Pos,f, /"‘ Step 3.1 ‘l for each Le HBp do compute Dep, 1(L); endfor /* Step 3.2 ‘/ endfor repeat /‘ Step 4: Compute T(I) ‘/ for each rule r in P do if Body, gnew_l and r is reliable w.r.t. I then add Head, to new_I; endif endfor until no change in new_1; compl_F={Le HBp l ~L is unreliable w.r.t. I}; I“ Step 5 *I repeat /" Step 6: Compute HBp -F(1) ‘/ foreach ruler inPdo if no literal in Body, is false w.r.t. I and all classical literals in Body, are in compl_F then add H, to compl_F; 34 endif endfor until no change in compl_F; for each Le I-IBP do I‘ Step 7*/ if Le compl_F then add ~L to new_1; endif endfor new_1=coh(new_1); /* Step 8: Compute coh(T(I)U~F (1)) */ until I=new__I; retum(I); } The complexity of computing Pas] is the same as that of computing the well-founded model of P when every literal -'L is replaced by a new atom —t_L. So, the complexity of Step 1 is [HBp|*]Rp| [78, 69]. The complexity of Step 2 is IIIBPI‘IRPI because the complexity of computing Dep1(L), for a literal L, is [RP]. The complexity of Step 3.1 is lRpl and that of Step 3.2 is lHBp|*|Rp|. So, the complexity of Step 3 is [ECRPIHBPPIRPL The complexity of Step 4 is llel‘lRp] since Pos,1 and Dep, 1(L), VLe HBp, have already been computed. The complexity of Step 5 is |ICp|*|HBp] < [ICpl‘lRp] and that of Step 6 is [RP] [19]. The complexity of Steps 7 and 8 is lHBp]. Since {la} is a monotonically increasing sequence w.r.t. c, the total number of iterations until I=new_1, is less than IHBp]. So, the complexity of the algorithm RM(P) is 0(IHBpl‘lRpl‘max(|ICp|, lHPpNECRI). 0 2.3.2 Stable r-models The reliable model of an EPP corresponds to its skeptical meaning. Credulous meanings can be obtained using the transformation Pl, 1, where I is an interpretation of P. The transfomration P/I for a normal program P is defined in [26, 60]. P/,I extends H] to EPPs. Definition 2.3.4 (transformation P/,I): Let P be an EPP and I be an interpretation of it. The program P1,! is obtained as follows: (i) Remove from P all rules that contain in their body a default literal ~L s.t. 1(L)=l. (ii) Remove from P any rule r with I(-'Head,)=l. 35 (iii) If r is a rule in P s.t. l(Body,)=l and I(Head,)=l/2 then replace r with Head,(—u. (iv) Remove from the body of the remaining rules of P any default literal ~L s.t. 1(L)=O. (v) Replace all remaining default literals ~L with u. (vi) lfI(L)=l/2 and ~L is unreliable w.r.t. I then add the rule Lt—u. (vii) Replace every classically negative literal “A with a new atom --._A. The program PI,I is a non-negative program with a special proposition it. For any interpretation J, J(u)=l/2. When P is a normal program and M is a model of P [60], PI,M a P/M since Steps (ii), (iii), (vi) and (vii) do not have any effect on PI,M. We say that a model M of P is the least, model of P ifi‘ M(L)SM'(L) for any model M' and classical literal L of P. The least, model of a non-negative program ean be obtained as the least, fixpoint of the ‘I’p operator [60] which generalizes the immediate consequence operator of [75]. Definition 2.3.5 (Pp operator) [60]: Let P be a non-negative program, I be an interpretation and A be an atom of P. ‘I’p(1) is defined as follows: (i) 'I’p(I)(A)=l if3 rule Ae—A1,....A,, inP s.t. I(A,-)=l, ViSn. (ii) ‘I’p(l)(A)=l/2 if ‘I’p(I)(A)¢l and 3 rule At—A1,...,A,, in P s.t.1(A,-)21/2, ViSn. (iii) 'I’p(l)(A)=0, othenvise. Definition 2.3.6 (stable r-model): Let P be an EPP and M be an r-model of P. M is a stable r- model of P ifl‘ least,(P/,M)=M. Stable r-models represent the credulous "meanings" of a program. For example, let P' be as the program P of Example 2.2.1 with be an EPP and is a stable r-model of P and Mp Q My. Proof: Let M be a stable r-model of P'. We will Show that every default literal which is unreliable w.r.t. M in P' is also unreliable w.r.t. M in P. Assume that ~L is unreliable w.r.t. M in P'. Since —e I2 _/ b d Figure 2.1: A digital circuit The circuit of Figure 2.1 consists of two inverters and one AND gate. To reason about its behavior, we give a simple formulation with an EPP, P=; Rp={ /* description of II gate */ r1: “cea,OK_Il. r2: ct—aa,OK__Il. /"‘ description of 12 gate “'/ r3: -d<—b, OK_12. r4: d(-—-'b, OK_12. /" description of Al gate ‘/ r5: et—c,d,OK_Al. r6: aet—cc,OK_Al. r7: net—ad, OK_AI. r8: a. l‘ a input has value 1 */ r9: "b. /" b input has value 0 ‘/ r10: e. l’ e output has value I *l /" assumptions that gates are working correctly*/ r“: OK_II. r12: OK_12. r13: OK_AI. S,,=Body,,, ViSl3}, ICp=BCp, and be an EPP which is free from default literals, S,={} V rule r, and 1C, =Bcp. Then, M is the skeptical c-partial model of P [24] ifiM is the set of classical literals in RMp. Proof: To simplify the proof, we redefine the operator T(J) of Def. 2.3.2 as follows: T(J)={L| 3 rule r in P s.t. Head,=L, Body,;J and r is reliable w.r.t. J}. Note that both definitions give equivalent reliable semantics. Let Ia=WpT“(0), for all a. We will show by induction that the set of classical literals in 1,, coincides with Slate), for all a. This is true when a=0. Suppose that it is true for all ordinals S a. We will show that the set of classical literals in 10+] coincides with SWIM). Since S(I)={L | a rule r s.t. Head,=L, Body, :1 and r is not c-defeasible w.r.t. 1}, it is enough to show that for each rule r, Body, :1, and r is reliable w.r.t. 1,, iff Body,t;ST“(0) and r is not c-defeasible w.r.t. Slam). 48 Body, 9:1,, and r is reliable w.r.t. Ia (From the inductive hypothesis and the fact that Body, is free of default literals, it follows that Body, :slalel.) iff Body, cSTato) and rule r is reliable w.r.t. 1,, (From the fact S, ={} V rule r and the reliable rule definition, it follows that r is reliable w.r.t. Ia ifl' (i) 3 no rule r' K r with Head,v = “Head, and Body,v :Posla or (ii) Body, is not a subset of P031“. Note that Body, gST“(0)<;Ia:Posla. ) iffBody, gSTaazl) and 3 no rule r' K r with Head,v = "Head, and Body,v UHead,v :Posla iff Body, :STato) and a no r' act with Head, = «Head, and (Body,.! UHead,v) n (HBp- P081a1=0 (Let r' be a rule in P with Body,v gPosIa. Then, r' is blocked w.r.t. 1,, iff *Head,v eIa ifi 3 r" K r' with Head,» = -Head,t and Body,» uHead,» gslaua). Consequently, Uctsla(0»=HBp —Pos 1,. ) iffBody, gslato) and a no r' K r with Head,v = -Head, and (Body,v UHead,v) n UctsTa(c))=o ifl' Body, gslato) and t is not c-defeasible w.r.t. Slam). o In [43], the well-founded partial model of an ordered logic program P is defined as follows: I A literal set S is unfounded w.r.t. an interpretation I ifl‘ VLe S, if r is a rule in P with Head,=L then either (i) 3 rule r' s.t. r' K r, Head,v = “Head, and Body,v (:1 or (ii) Body, n S at: 0. 0 A rule r is defeasible w.r.t. I ifl‘ 3 rule r' s.t. r' K r, Head,v = '"Head, and Body,.! n U(I) = 0, where U(I) is the greatest unfounded set w.r.t. I. o The well-founded partial model of P is the least fixpoint of the monotonic operator S(I)= {Ll 3 rule r in P s.t. Head,=L, Body,t;I and r is not defeasible w.r.t. 1}. Similarly to [24], rule ordering in [43] represents exceptions and not reliability. This corresponds in our fiamework with the case that S,={} V rule r. Indeed, the reliable model ofthe program P in Example 2.3.3 with S,={} V rule r, is the same as the well-founded partial model of P. Another difference between the reliable model and the well-founded partial model is 49 demonstrated by the following example: The well-founded partial model of P={p. apt-q. "q. q.} with be an EPP which is flee from default literals, S,={} V rule r, and ICp =BCp. Then, the set of classical literals in RMp is a subset of the well-founded partialmodel of P [43]. The mle ordering