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

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

> > > That said, I should say that I admit the possibility that you might be able
> > > to tweak your definition so that it will become asymmetric. But I doubt
> > > that there is a "useful" sense (now I am being informal :-) in which
> > > constraints can be defined in pure FOL.
> > 
> > Well, now, this is a different question.  However, in fact, I do believe
> > that one could come up such a definition.  It might not be pretty, and it
> > might not be completely stock FOL (e.g., it might require that constraints
> > be formulae, and talk about a substitution of names into constraints), but
> > it probably could be done.  I'm not about to spend the effort, however, as
> > I think that an epistemic framework for constraints is better.
> 
> Well, this was my main point. Whether epistemic or a form of CWA, it is not
> first-order.

Agreed.  At least in the sense that FOL is not the ideal framework for
constraints.

> 	--michael  

peter

Received on Tuesday, 25 April 2006 15:50:16 UTC