答辯提綱

1、Assertion Answer Set Logic Program and its Application,Mingyi ZhangGuizhou Academy of Science2012-6-18,Motivation,(1) Lack of intuition Noncumulativity (Brewka,1991; Giorddano and Martelli,1994) Cause : I

2、nconsistency between justification of defaults ( does not commit to assumptions) Example 1 Broken-arm (Pool, 1988) :Useable(x)?¬Broken(x)/Useable(x) (1) Broken(Leftar

3、m)?Broken(Rithtarm)E=Th(Broken({Leftarm)?Broken(Rithtarm), Useable(Leftarm), Useable(Leftarm)}),Motivation,,Motivation,Adding the information ?x.BROKEN(x) ?USABLE(x) , (3)will generate two extensions as

4、 desired. This is a type of "hard" exceptions to a default, i.e. exceptions for which the negation of the default's consequent can be proven. In this case (1) can be replaced by :Useable(x)/Useabl

5、e(x) But we hope to consider a weaker type of exception to a default: we want to block a default but we don't assert the negation of its consequent. Nonnormal defaults are needed precisely to express this we

6、aker type of exceptions.,,Motivation,Example 2 (Brewka, 1991) DOG ? BIRD? PET DOG?¬BIRD PET:DOG/DOG SINGS:BIRD/BIRD S1NGS . E=Th(W?{BIRD)}) which

7、 contains PET Adding PET to the DT, we get another extension which contains DOG.,,Motivation,(2) Destroy part of the additional expressiveness of nonnormal defaults CDL is cumulative and commits t

8、o assumptions. However, CDL is in the style of Lukaszewicz's default logic. It happens to be semimonotonic, which destroys part of the additional expressiveness of nonnormal defaults, for instance, it makes it imposs

9、ible to represent priorities among defaults.,,Motivation,Example 3 (Giorddano and Martelli,1994) student :¬ married/¬married (1) adult : married/married (2) living-in-college :

10、 student/student (3) beard : adult’adult (4) living-in-college beard We want default (1) to have a higher priority than default (2). To achieve this purpose, default (2)

11、can be replaced with the seminormal default:adult : married?¬student/) married (2’),,Motivation,The resulting theory has a single DL extension, Th({living-in-college, beard, student, adult, ¬married}), as wa

12、nted, since applying default (3) blocks (2'). This same theory, however, has two CDL extensions:F 1 containing (adult : (adult}), (married : (adult, married?¬student} ) and:F 2 containing (student: {student})

13、, (adult : {adult}), (¬married :{student,¬married}), since in CDL (3) blocks (2'), but (2') blocks (3) in turn. Hence, in CDL, using seminormal defaults does not allow to enforce priorities among

14、default rules (1) and (2), as in Reiter's default logic.,,Motivation,To do this, Giorddano and Martelli introduced CADL (Commitment to Assumption Default Logic) and QDL(Quasi-Default Logic). Guaranteeing cumulativity

15、 of QDL, they imposed a condition on definition of QDL extension. Zhang (1999) gave the definition similar to Reiter’s one, algorithms for reasoning task for CADL and QDL, and a sufficient and necessary condition for cu

16、mulitiviy of QDL. (2010),,Motivation,(3) Keep trace of an inference supporting a conclusion Abduction A?B, B --------------- A I. Proof in Geometry   II. Diagno

17、sis based on consistency (Reiter 1980),,Motivation,A system is a pair (SD, COMPS), where SD, the system description: a set of first-order sentences COMPS, the system components: a finite set of constants. A

18、n observation of a system is a finite set of first-order sentences(SD, COMPS, OBS) ---- a system (SD, COMPS) with observation OBS.A diagnosis for (SD, COMPS, OBS) is a minimal set ??COMPS such that SD ? OBS

19、? {AB(c) ? c ??} ? {?AB(c) ? c ? COMPS??} is consistent.,,Motivation,Proposition 1 (Zhang mingyi et al, 2004) Let (SD,Comps) be a system and OBS an observation. ?Given ??COMPS), if SD?OBS?{??AB(c)? c?COPMPS-?} is

20、consist, and for any ci?? , is a diagnosis for any ci??, SD ? OBS ? {?AB(c)?c ?COMPS??}╞ AB(ci), then ? is a diagnosis for (SD, COMPS, OBS).Proposition 2 (Reiter, 1987) ---- Relation between Diagnosis and premise-free

21、normal DL Consider a system (SD, COMPONENTS) under observation OBS, where so and OBS are sets of first-order sentences. Then E is an extension for the default theor yDT =( {:¬ AB(c)/ ?AB(c)? c ?COMPS}, SD ? OBS

22、) iff for some diagnosis ? for (SD, COMPONENTS, OBS), E = {?? ? predicts II}.,Assertion ASP,(1) ASP--– a special case of DL Assertion ASP---a special case of QDL in Reiter’s senseDefinition 1 An assertion is a

23、n expression of the form , where L and S are a literal and a set of literals respectively. For any set of assertions W, we denote: Form(W)={L| }, the set of literals of W. Supp(W)= , the support of W.In p

24、articular, Form(A)={L} and Supp(A)=S are the literal and support of A, for an assertion A=.,Assertion ASP,Definition 2 A rule is an expression of the form L0←L1,L2, ...,Lm, not Lm+1, …, not Ln(m+n>0), where L0, Li (1≤

25、i≤n) are literals respectively. For a set of rules R, we use the following notations:Head(R)={L0|L0←L1,L2, ...,Lm, not Lm+1, …, not LnR(m+n>0)}Pos(R)= {Li|L0←L1,L2, ...,Lm, not Lm+1, …, not LnR,1≤i≤m,(m+n>0)}Neg

26、(R)= {Li|L0←L1,L2, ...,Lm, not Lm+1, …, not LnR,m+1≤i≤n,(m+n>0)}Write a rule as Hed?Pos, not Neg. A rule r is basic if Neg(r)=? .Definition 3 Π=W∪R is an assertion answer set program (AASP) if W is a set of assert

27、ions and R is a set of rules. Π=W∪R is basic if R is a set of basic rules. Π is finite iff W and R both are finite.,Assertion ASP,Definition 4 Let Π=W∪R be an AALP. A set of assertions E is an answer set of if E=∪0≤i

28、Ei , Where E0=W if Form(W) is consistent, otherwise {}, Ei+1=Ei∪Fi if Form( ) is consistent, otherwise {}.where Fi={|L0←L1, L2, …, Lm∈R and ∈Ei for 1≤ j≤m}.Definition 5 Let ?=W?R be an AASP and F a set of

29、 assertions . The F-reduct ?F is an AASP obtained by removing each r?R if Neg(r)? Form(F) ??.,Assertion ASP,Definition 6 Let E is an answer set of Π=W∪R . The set of generating rules for E, GD(E,Π), is the set {L0←L1,L2

30、, ...,Lm, not Lm+1, …, not Ln∈R,(m+n>0)|for i:1≤i ≤ m,∈E and for j:m+1≤j≤n,Lj?Form(E)}.Definition 7 Let ?=W∪R be an AASP. For any R???,. we define an operator ?: ?(R?,?)=∪n?0 ?n(R?,?), as follows: { Head?

31、 Pos, not Neg ?R ? Form(W)∪{Head} is consistent}, ?0(R?,?)= {}, otherwise   {Head?Pos, not Neg?R ? Pos? Form(W)∪Head(?n(R?,?) ) and Pos? Form(W)∪Head(?n(R?,?)) is

32、consistent T?n+1(R?,?)= {?L?Lit} otherwise,Assertion ASP,Definition 8 Let ?=W?R be an AASP. R??R is compatible (w.r.t. ?), if , for any L?Neg(R?), L?Form(W)?Head(R?). R’ is strongly compatible if R’ is compatib

33、le and ?(R ?, ?)=R?. R’ is ?-robust (or just robust, if A is understood), if R’ is strongly compatible and, for any R??? R?, if R?? is strongly compatible, then R??=R?.Corollary 1 ? has an inconsistent answer set iff

34、 Form(W)?Head(?(R*,?)) is inconsistent, where R*={r?R?Neg(r)=?.Corollary 2 E={} is an answer set of ? iff Form(W)?Head(?(R*,?)) is inconsistent.Corollary 3 Suppose E is an

35、 answer set of ?. Then Form(E) =Form(W)?Head(GR(E,?)) , Supp(E)=Supp(W)?Neg(GR(E, ?)),Assertion ASP,Theorem 1. (Characterization of assertional answer sets) Let ?=W?R be an AASP. ? has an

36、 answer set iff there is a strongly compatible subset R? of R such that, for any r?R?R?, Pos(r) ?Form(W)?Head(R?) or (Form(W)?Head(??))? Neg(r?) ??.Corollary 4 If R is compatible then ?=W∪R has a unique answer set.,Ass

37、ertion ASP,Based on the characterization we can give an algorithm for computing answer sets and its complexity. Now we deal with the following problem, which we call the membership problem: Given an AASP ?, a robust set

38、?' and an assertion , determine whether is an element of the answer set generated by ?'.The main reasoning tasks in AASP are skeptical reasoning (SR) and credulous reasoning.? SR: Decide whether a given asserti

39、on occurs in all assertional answer sets of ?.? CR: Decide whether a given assertion occurs in some assertional answer set of ?. We derive some formal results that will allow us to deal properly with supports and to

40、solve the membership problem.,Assertion ASP,Definition 6 Let S be a support, ? an AASP, and F a set of assertions. Then ?[S] = {r?? ?Neg(r)?S}, F[S] = {?F ?V?S}Lemma 1 Let ? be an AASP. If R is compatible, the

41、n it has a unique answer set E and GD(E, ?) = ?(R,?).Lemma 2 Let E be an answer set of a finite AASP ? and an assertion in E. Then the assertion is also an element of E. From the definition of AASP extension, o

42、ne may be tempted to think that reasoning in AASP requires exponential space, due to the combinatorial explosion of the supports in the intermediately generated assertions. However, in this paper we show that AASP has t

43、he same complexity as ASP.,Assertion ASP,Theorem 2 Let ? be a finite AASP, ?' a ?-robust set of rules, and an assertion . Let ?S=?'[S]. Then is an element of the answer set E' of ? generated by ?' iff t

44、he following two conditions (1) and (2) are satisfied:(1) L?Head(?(?'[S],?S));(2) Neg(?(?'[S],?S)) = S.Theorem 3 Let ? be a finite AASP and let be an assertion and S??. (1) If Head(?(?B)) is inconsistent, t

45、hen is not an element of any assertional answer set of ?..(2) If Head(?(?B)) is consistent, the AASP ?S has a unique answer set E with set of generating rules GD(E) =?(?S). The assertion is an element of some extensio

46、n of ? iff ?E.,Assertion ASP,Lemma 3. Let ? be a finite AASP and an assertion such that Head(?(?B)) is consistent. Then, belongs to some answer set of ? iff for every ?, ?(?S)????S , it holds that(1) ?Head(?), and(2)

47、 Neg(?) = R, where ?S=?'[S].Theorem 4. In propositional AASP the reasoning tasks SR is NP-omplete, while the reasoning task CR is DP-complete.Theorem 5 AASP is cumulative.,Assertion ASP,Splitting (Wu Maonian and

48、Zhang Mingyi) Based on the Finest Splitting of Belief Set and the characterization of AASP answer sets we explored a method, which constructs a reduce without guessing a set of assertions.,Assertion ASP,Applications

49、,(1) Alias analysis (Yang Bo and Zhang Ming) Find a well tradeoff between precision and computation cost of alias analysis for some programming languages. Alias in Java program is one of the main causes for pro

50、gram errors. Applying AASP can determine the propagation path of points-to information more accurately, and hence improve the precision of points-to analysis.,Application,Application,ASP Rules for Points-to Analysis,ref

51、(x,o,cs,s')←pred(s,s'), ref(x,o,cs,s), not ¬ref(x,o,cs,s') (r1)reff(o,f,o',cs,s')←pred(s,s'), reff(o,f,o',cs,s), not ¬reff(o,f,o',cs,s')

52、 (r2)ref(x,os,cs,s)←new(s,os,x), call(m,c,cs,cs'), in(s,c,m), not inbranch(s) (r3)ref(x,os,cs,s)←new(s,os,x), call(m,c,cs,cs'), in(s,c,m), pred(s1,s2), if(s1),

53、 branch(s2,s1), inbranch(s), same(s2,s) (r4)¬ref(x,o',cs,s')←pred(s,s'), new(s',o,x), ref(x,o',cs,s) (r5)ref(x,oy,cs,s')

54、←pred(s,s'), ref(y,oy,cs,s), asn(s',x,y) (r6)¬ref(x,ox,cs,s')← pred(s,s'), ref(x,ox,cs,s), asn(s',x,y), not sp(s') (r7)reff(ox,

55、f,oy,cs,s')←pred(s,s'), ref(y,oy,cs,s), ref(x,ox,cs,s), store(s',x,f,y) (r8)¬reff(ox,f,o,cs,s')←pred(s,s'), ref(x,ox,cs,s), reff(ox,f,o,cs,s),

56、 store(s',x,f,y), not sp(s') (r9)ref(y,o,cs,s')←pred(s,s'), ref(x,ox,cs,s), reff(ox,f,o,cs,s), load(s',y,x,f) (r10)¬ref(y,oy,cs,s')←pred

57、(s,s'), ref(y,oy,cs,s), load(s',y,x,f), not sp(s') (r11),Application,sp(s')← pred(s,s'), ref(x,ox,cs,s), ref(y,oy,cs,s), ox=oy , asn(s',x,y) (r12)sp(s')←pred(s,s

58、'), ref(x,ox,cs,s), reff(ox,f,o,cs,s), ref(y,oy,cs,s), o=oy, store(s',x,f,y) (r13)sp(s')←pred(s,s'), ref(y,oy,

59、cs,s), ref(x,ox,cs,s), reff(ox,f,o,cs,s), oy=o, load(s',y,x,f) (r14)1{pred(s,s'):branch(s',s)}1←if(s)

60、 (r15),Applications,Definition 9 Let P is a program and R a set of rules. R is sound w.r.t. a point—to relation of P if, for any statement St?P with corresponding n

61、ode s in a control flowchart such that ∈PT[St], 1) for any reference x occurring in P, if σ′ x=ox，then ref(x,ox,cs,s) ∈Rule(s)； 2) for any reference-type variable with a form x.f, if σ′ x=ox and σ′ ox.f=o，then ref(x

62、,ox,cs,s)∈Rule(s) and reff(ox,f,o,cs,s)∈Rule(s),where PT：Stm→(PS?PS) is a point-to semantic relation, PS is the set of all point-to states and Stm is a set of statements formed by Assignment statement , Skip, Load, Sto

63、re, Sequential Compound statement, Conditional statement and While statement.,Applications,Theorem 3 The set R of rules is sound w.r.t. inference of points-to relation on a program. For a diagnosis system (SD, COMPO

64、NENTS,OBS)，we call ?=?* ∪ C∏ the program corresponding to the diagnosis system, where ?*={ L0←L1,…, Lm? L0??L1?…??Lm? CL?OBS, m?0}?R and C∏= {←L1,…, Lm? ?L1?…??Lm?CL?OBS, m?1}.Definition 10 Given a diagnosis system DIS

65、=(SD, COMPONENTS, OBS) and its corresponding standard program ?=?* ∪ C∏ , ? a diagnosis for DIS if there is an answer set S of ? such that,Applications,From Theorem 1 we haveTheorem 4 is a diagnosis for DIS= (SD,

66、COMPONENTS, OBS) iff is a minimal subset of COMPONENTS such that I. ?(??)=??, where ??={r??*?H(r)?COMPONENTS- } and ? is a standard program corresponding to DIS,II. CL?OBS??? ) is consistent

67、.,Applications,Deal (Chen Wu, Zhang Dongmo and Zhang Mingyi) Definition 11 A bargaining game is a pair ((?1, ? 1),(?2, ? 2)), where ?i (i=1,2) is an AASP and ?i is a complete transitive and reflexive order (total

68、preorder or weak order) over ?i that satisfies the following condition: for r, r1,…rn ??i, If Pos(r)?? and Pos(r)?Head({r1,…rn}) then there is k (1?k?n) such that rk ?ir.The pair (?i, ?i i) is called the prioritized

69、demand of player i. For any r, t??i, r?i t denotes that r ?i t and t?i r. r≈it denotes r?i t and t?i r. Clearly, ≈i is an equivalent relation on ?i, which uniquely determines a partition of ?i. We use ≈i to give a hie

70、rarchy of ?i, that is, each equivalent class is viewed a level of the hierarchy.,Applications,Definition 12 The sets of assertions E1 and E2 are co-consistent if both Form(Ei)?Form(E-i) and Form(Ei)?SuppE-i) are consiste

71、nt, where –i=3-i. Definition 13 Given a prioritized demand set (?,?) for an agent, its hierarchy {(?j)}j?1 is defined as follows: ?1={r????t?? (r?t)}; ?1=???1. for k?1 ?k+1={r??k??t??k (r?t)}; ?k+1=?k ??k+1. I