Re: SNAF, NAF, and monotonicity [was: Comments on * DRAFT * Rules...]

> This is a multi-part message in MIME format.
> --------------090306020606020604000604
> Content-Type: text/plain; charset=us-ascii; format=flowed
> Content-Transfer-Encoding: 7bit
> 
> Ok, let me rephrase what I tried to say:
> 
> 1. There is obviously something about SNAF, CWA and non-monotonicity 
> that led Sandro to write a contradictory draft, Dan to refuse that 
> 007car be yellow and me to make a fool of myself (well, the latter may 
> not have anything to do with SNAF, CWA or non-monotonicity, actually);


There is nothing mysterious about it. We all know some things better than
others and make mistakes.


> 2. A useful way to think informally about CWA is as if it were an 
> inference rule (just out of curiosity, is there a short explanation, or 
> a pointer towards a long one, why it could not be an inference rule, 
> actually?): that way, I can see clearly why adding a fact can make 
> previous consequences false (from a purely deductive point of view, so, 
> without having to think about interpretations);


Inference rule is a useful way to think of it at an intuitive level.
However, the only version of CWA that is defined as an inference rule that
I know of is NAF. Not what is being called NAF in this discussion thread,
but the real NAF, as in Prolog.

All the other popular versions of CWA (well-founded, stable,
circumscription) use model-theoretic definitions or axiomatic.

> 
> 3. A fallacious way to think about CWA --a big no-no, don't do that, 
> ever, it doesn't make sense, anyway; but, still, sometimes you cannot 
> help-- is to assume that the world is really closed, and that we have 
> complete knowledge about it, and thus that we can act as if all the 
> missing negated facts were there, and then we just work with good ol' 
> classical negation. And then, of course, it happens that we forget that 
> it is just an assumption and, so, we are not happy when reality breaks 
> in and adds some facts that contradict the assumed negated facts (we are 
> unhappy because it contradicts our initial closed world assumption, not 
> because of the non-monotonicity). Could it be that Dan was careless 
> enough to trip into that kind of fallacy, at early some point in the 
> discussion?

I don't know. But usually it is impractical or impossible to have all the
negative facts listed.


> 4. On the other hand, this is what monotonic inference mechanisms do, 
> for all practical purpose: within the scope of the assumed closed world, 
> they reason monotonically; when the closed-world assumption is broken or 
> before it breaks, for whatever reason (and, possibly, because of actions 
> triggered by the inference system itself, as in a production rules 
> engine), the engine is made to stop and, if and when more inference are 
> needed, to restart with the new initial conditions. That's 
> non-monotonicity all right, if you consider the whole system, including 
> the part that causes the engine to stop when or before the CWA is 
> broken; but if you consider things from inside the inference engine, 
> there is nothing but monotonicity.
> 
> (see attached use case scenario: thanx to point out what is wrong with 
> it and why, if something is).

It is a good use case, but you are misapplying the definition of
monotonicity, if I understand your example correctly.

What you are doing is this:
You have a state S1 and you are making an inference F:

    S1 |= F

Then you assert F (whatever changes you made to the cars) and get to a new
state S2=S1+F.

Then reality badges in and some new fact B is added. So, you get a new state:
S3 = S2 +B.

Then you are checking whether S3 still entails F, and sure enough it does.
So, you conclude it is monotonic. But here you have "monotonicity" for
formulas of a certain kind (the same problem as Dan had), not for all
formulas. As far as I recall, according to so called Gabbay's postulates,
*every* *non*monotonic logic also has the property that if S |= F then
S+F+something |= F.
In any case, the most popular CWA flavors (the well-founded and stable
models) do have the above property.
So, your argument in the use case doesn't establish anything as far as
monotonicity goes.


> 5. It is clear to me that NAF is needed if we want the RIF to be of 
> practical use. It is clear to me as well that the scope of NAF may need 
> to be specified in some way when sharing rules.
> 
> Now, what is not clear to me, is: what kind of features specific to 
> non-monotonicity does a rules interchange format need to have, to deal 
> with that use case, besides the capability to unambiguously specify the 
> scope of a NAF? More generally, what is not clear to me is: what kind of 
> features are needed in a RIF wrt non-monotony, besides the capability to 
> specify and scope unambiguously the nonmonotonicity-generating features 
> in a rule (such as NAF, default, etc)?

This depends on the nature of the RIF. If the charter envisions it as
Sandro explained originally (that most rule languages and FOL could be
mapped into that RIF in semantically-preserving way) then the charter is
likely defining an empty set of RIFs. If the charter doesn't insist on that
then there is room to improvise. I suspect that the end result will be
something like RuleML then.

> If the answer to the first question is: none, couldn't we repair the 
> draft charter (wrt that issue) by removing section 3.1 and rephrasing 
> section 2.9 to say that SNAF is in scope and the RIF must offer ways to 
> specify the scope of NAF. That is, after section 2.3 has been amended to 
> avoid the contradiction between such a statement and the RIF being full 
> FOL, of course.

It is really not a matter of scope. NAF with scope has basically the same
properties as NAF without explicit scope. It is just more convenient in Web
environment and more versatile.

What we should do is to remove the clause that NAF is out of scope and
remove the reference to monotonicity. Then let the WG deal with it.


	--michael  


> 
> Michael Kifer wrote:
> >
> > [...]
>  >
> > We don't need to care about anything. We just need to understand what the
> > issues are and be aware of simple things that have been known for decades.
> > 
> > This whole thread started because the draft charter contained several
> > contradictions. Clearly, it is not healthy to base one's work on a document
> > that is internally contradictory. All we did was to point this out.
> 
> Once you pointed out that, the issue becomes that there must be a reason 
> why the draft charter says that SNAF is in scope, but that NAF and 
> non-monotonicity are out.
> 
> So, the interesting questions are: can we remove the contradiction and 
> keep the intention,? And, if yes, how? And, btw, what was the intention?
> 
> Just for the avoidance of doubt: my postings on this issue are meant to 
> make progress on these questions (whether they do is something 
> different, yet), not to question the foundations of formal logic, model 
> theory or whatever.
> 
> Christian
> 
> --------------090306020606020604000604
> Content-Type: text/html;
>  name="Use_case_car_planning,_CWA_and_monotonicity.html"
> Content-Transfer-Encoding: 7bit
> Content-Disposition: inline;
>  filename="Use_case_car_planning,_CWA_and_monotonicity.html"
> 
> <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"><html><head><meta http-equiv="content-type" content="text/html; charset=ISO-8859-1"><title>Use
>  case car planning, CWA and monotonicity</title></head><body>Car planning, CWA and monotonicity<br>
> <br>
> The production policy of a car manufacturer is that a particular car
> starts being built as soon as it is ordered (if it could not be sold
> from the available stock). Default rules determine how the
> manufacturing capacity is to be used, beyond that specific case (that
> is, what cars have to be built for stock): these rules decide, in
> particular, what is the color mix needed to replenish the stock (which
> is an important factor, as it severely affects car sequencing). The
> rules are updated from time to time, based on market and stock data,
> and published by the marketing dept towards the production units. At
> production unit U, the production plan is prepared once a day, then
> production is scheduled accordingly. Prior to start sequencing, the
> scheduler fills in the specifications for the cars to be produced, from
> the order list and the rules.<br>
> <br>
> One morning at unit U, the rules might look like this:<br>
> <br>
> for all cars x to be produced that day, ordered(x) -&gt; (orderColor(x, y) -&gt; makeColor(x,y))<br>
> for all cars x to be procuded that day, ~ordered(x) -&gt; makeColor(x,black)<br>
> <br>
> and U's order list contains:<br>
> ordered(001), ... ordered(006)<br>
> orderColor(001,green), ... orderColor(006, blue)<br>
> <br>
> Initially, like every morning, the specification list only contains (U's daily production capacity is 100): car(001),...car(100)<br>
> <br>
> So, the scheduler initialises the specs, and then starts sequencing 6
> colored cars and 94 black ones, when the order list is updated by the
> sales dept, adding:<br>
> ordered(007), orderColor(007,yellow)..<br>
> <br>
> If the scheduler is capable of non-monotonic reasoning, it will be able
> to repair the sequence to replace the production of one of the black
> cars by the production of a yellow one. If not, it will just ignore the
> update, and deal with it the day after (units have different schedulers
> and thus different ways to deal with that issue).<br>
> <br>
> Every night, the cars produced in the day are compared to the
> specifications in the ordered list, and delivered if they fit one order
> or stocked if they do not (or thrown away if they do not fit the spec
> of any car in the prod list either) and the order list is reinitialised
> for the next day (in the case where car001 to 006 have be produced
> according to orders, the list is reinitialised to: ordered(001),
> orderColor(001, yellow) etc; dependeing on the orders received that
> day).<br>
> <br>
> Discussion:<br>
> The negation in ~ordered(x) in the second rule is a NAF, scoped to U's
> order list of the day. Suppose any unit can access the order lists for
> all the order units as well, the scope of the NAF must be made explicit
> when publishing the rule, lest a naive unit looks everywhere it can for
> ordered cars, including in other units order lists.<br>
> The whole system is nonmonotonic, since orders can be added to the list
> at any time. The retrieving application needs or need not care about
> that nonmonotonicity, depending whether it schedules monotonically,
> based on a snapshot of the order list once a day, or&nbsp; whether it
> is able to reschedule dyanmically, repairing the current schedule when
> it is falsified by a new entry in the order list.<br>
> <br>
> </body></html>
> --------------090306020606020604000604--
> 
>

Received on Thursday, 1 September 2005 07:03:08 UTC