Re: [RIFWG] [Requirements?] A vision for the RIF

Peter F. Patel-Schneider <pfps@research.bell-labs.com> wrote:
> 
> From: Michael Kifer <kifer@cs.sunysb.edu>
> Subject: Re: [RIFWG] [Requirements?] A vision for the RIF 
> Date: Tue, 25 Apr 2006 10:56:01 -0400
> 
> > 
> > > From: Michael Kifer <kifer@cs.sunysb.edu>
> > > Subject: Re: [RIFWG] [Requirements?] A vision for the RIF 
> > > Date: Tue, 25 Apr 2006 09:28:12 -0400
> > > 
> > > > 
> > > > > From: Michael Kifer <kifer@cs.sunysb.edu>
> > > > > Subject: Re: [RIFWG] [Requirements?] A vision for the RIF 
> > > > > Date: Mon, 24 Apr 2006 22:44:24 -0400
> > > > > 
> > > > > > 
> > > > > > Peter F. Patel-Schneider <pfps@research.bell-labs.com> wrote:
> > > > > > >
> > > > > > > From: Michael Kifer <kifer@cs.sunysb.edu>
> > > > > > > Subject: Re: [RIFWG] [Requirements?] A vision for the RIF 
> > > > > > > Date: Mon, 24 Apr 2006 14:13:09 -0400
> > > > > > > 
> > > > > > > > 
> > > > > > > > > From: Michael Kifer <kifer@cs.sunysb.edu>
> > > > > > > > > Subject: Re: [RIFWG] [Requirements?] A vision for the RIF 
> > > > > > > > > Date: Mon, 24 Apr 2006 12:15:24 -0400
> > > > > > > > > 
> > > > > > > > > > 
> > > > > > > > > > 
> > > > > > > > > > > Michael Kifer wrote:
> > > > > > > > > > > > I said that normative rules imply that we must use some sort of a closed
> > > > > > > > > > > > world assumption. Under the open-world assumption there is no useful way to
> > > > > > > > > > > > distinguish between normative rules and deductive rules, but under the CWA
> > > > > > > > > > > > there is.
> 
> [...]
> 
> 
> > > > > > > > > I'm not sure why it is necessary for constraints to be interpreted in a CWA
> > > > > > > > > environment.
> > > > > > > > > 
> > > > > > > > > In particular, I don't see why the following development is not suitable:
> > > > > > > > > 
> > > > > > > > > Given a logical language (e.g., FOL or Horn rules), consisting of a syntax
> > > > > > > > > 	for axioms (e.g., FOL statements or ground atomic facts plus Horn
> > > > > > > > > 	rules) in the language and a model-theoretic semanticsbased on a
> > > > > > > > > 	set of interpretations and a primitive satisfaction relationship
> > > > > > > > > 	written i |= a, with i an interpretation and a an axiom (e.g.,
> > > > > > > > > 	Tarskian FOL semantics or some minimal-model semantics for Horn
> > > > > > > > > 	rule).
> > > > > > > > > 
> > > > > > > > > Let a KB = < S, C > be a pair of two sets of axioms (the statements and
> > > > > > > > > 	the constraints of the KB) 
> > > > > > > > > 
> > > > > > > > > Define the meaning of a KB = < S, C > as
> > > > > > > > >  	bottom if there is some interpretation i that satisfies each s in S
> > > > > > > > >                but there is some c in C where i does not satisfy c;
> > > > > > > > > 	{ i | i |= s for all s in S } otherwise
> > > > > > > > > 
> > > > > > > > > Yes, this is not what LP people think of as their way of working with
> > > > > > > > > constraints, but I don't see why it is not an acceptable way of thinking
> > > > > > > > > about constraints.
> > > > > > > > > 
> > > > > > > > > peter
> > > > > > > > 
> > > > > > > > Because you defined precisely the set of models of S union C. Right?
> > > > > > > > That is, there is no difference between S and C whatsoever. This was
> > > > > > > > precisely my point.
> > > > > > > > Under FO semantic, there is no difference between deduction and
> > > > > > > > constraints and the distinction is completely arbitrary.
> > > > > > > > You might as well call S "normative" and C "deductive" or
> > > > > > > > S union C "normative" or "deductive", or both. 
> > > > > > > 
> > > > > > > Not so, my definition distinguishes between two things: bottom - which
> > > > > > > results from a constraint violation - and unsatisfiable - which is defined
> > > > > > > in the more-usual manner.
> > > > > > > 
> > > > > > > Consider a FOL version of the above 
> > > > > > > and look at S = { p(a) } and C = { ~p(a) }.  
> > > > > > > The meaning of < S , C > is bottom, because there are interpretations that
> > > > > > > satisfy p(a) but do not satisfy ~p(a).  
> > > > > > > The meaning of < S u C, {} > is the (empty) set of interpretations that
> > > > > > > satisfy both p(a) and ~p(a). 
> > > > > > 
> > > > > > And the meaning of <C,S> is also bottom. So, C and S are interchangeable,
> > > > > > which was exactly my point - there is no real difference between deductive
> > > > > > and normative formulas in FOL.
> > > > > 
> > > > > Not so.  The meaning of <C,S> is the empty set of interpretations, a
> > > > > perfectly good value in the set of sets of interpretations, which is
> > > > > different from bottom, which is an "extra" possibility for the meaning of a
> > > > > KB. 
> > > > > 
> > > > 
> > > > I think you would have to change your definition in order for what you said
> > > > to be correct. According to what you wrote above, to have the meaning
> > > > "bottom" I need to show an interpretation, which satisfies every c \in C
> > > > (i.e., ~p(a)) but doesn't satisfy S (i.e., p(a)). Since, in fact, any
> > > > interpretation of C is such that S is not satisfied, the meaning is
> > > > "bottom".
> > > 
> > > Why does the meaning of a KB always have to be a set of interpretations?
> > > I meant bottom in the sense of "error", which is not a set of interpretations.
> > 
> > I understood "bottom" to mean an "error". I just used your own definition
> > to illustrate that for your example the meaning of both <S,C> and <C,S> is
> > bottom. So, your definition is symmetric with respect to constraints and
> > thus doesn't distinguish them from regular formulas.
> 
> Not so.  
> 
> It is true that if S and C don't entail each other then the meaning of
> <S,C> is the same as the meaning of <C,S>.  However, there are lots of
> Ss and Cs where the meaning of <S,C> is different from the meaning of
> <C,S>.  Consider, for example, 
> 	< {p(a),p(b)}, {p(a)} > 
> and 
> 	< {p(a)}, {p(a),p(b)} > 
> 

OK, I concede that your definition is not symmetric with respect to S and
C.  But I don't think that you would argue that the above is also a
suitable definition. In my original message I argued that in practice
people specify constraints that are not entailed by the derivation
rules. So, in the above example one might have the KB {p(a)} and the
constraint would be {p(b)}, not {p(a),p(b)}. (That is, people find it to be
odd to have to also state that p(a) as part of the constraint because it is
implied by the KB.)

Anyway, you agreed that FOL is not the right framework for constraints,
and my intent was to raise awareness of this. It was clear from the many
emails that a number of people didn't quite realize that.


	--michael

Received on Tuesday, 25 April 2006 17:03:02 UTC