Dagstuhl Seminar: neg-defeasible rules and naf rules

From: Harold Boley (boley@informatik.uni-kl.de)
Date: 03/07/02


Hi all,

on Tuesday we discussed closed/open world assumptions, negation
as failure vs. explicit negation, non-monotonic logic, defeasible
inference, etc., as inspired by the "rules" Dagstuhl Seminar
(http://www.dfki.uni-kl.de/ruleml/rmt/program/).

I promised Richard some background material on the talk by

Grigoris Antoniou, Universitšt Bremen:
Efficient Defeasible Reasoning
(http://www.informatik.uni-bremen.de/~ga/research/ruleml.html)

Grigoris' talk among other things discussed whether one can get
rid of two kinds of negation by introducing defeasible implication.

Another interesting Dagstuhl talk related to these topics was by

Michael Schroeder, City University London:
Arguments and Misunderstandings:
A Fuzzy Approach to Conflict Resolution in Open Systems
(http://www.soi.city.ac.uk/~msch/talks/fuzarg)

Let me discuss here the basic idea of such rule systems and start to
compare it with description logics, instantiating and elaborating an
example discussed by

Xianchang Wang, Jia-Huai You, and Li Yan Yuan:
Logic programming without default negation revisited (page 4)
http://web.cs.ualberta.ca/~yuan/papers/1997/icips97.ps

Let me use these conventions:

Negation as failure will be be denoted by:    naf
Explicit negation will be be denoted by:      neg

Defeasible implication will be be denoted by: <=
Ordinary implication will be be denoted by:   <-

Now, attempts have been made to transform a "naf rule" like

  p(x)      <-  q(x)  ^  naf(r(x))

into "neg-defeasible rules" like

  p(x)      <=  q(x)

  neg(p(x)) <=  r(x)

where the case of conflict (contradiction) of the "neg-defeasible rules"
corresponds to the case of non-applicability of the "naf rule":
In a "sceptical" view, if both rules are potentially applicable with the
same substitution, none of them will be applied.

The negative head of a predicate definition, here neg(p(x)), from the
'exception-case' rule, has also been considered to have priority over
its corresponding positive head, here p(x), of the 'normal-case' rule.

Such priorities are often made explicit:

1:    p(x)      <=  q(x)

2:    neg(p(x)) <=  r(x)

1 < 2

Priority labels can also be used for other purposes such as contractual
exception rules, and are useful quite independently from attempts to
replace naf. They were thus brought into RuleML by Benjamin Grosof.

Now, for instantiating the transformation of the example, let us first
assume three often-used predicate assignments:

p = can-fly
q = bird
r = penguin

The "naf rule" instantiation

  can-fly(x)      <-  bird(x)  ^  naf(penguin(x))

can be transformed into the "neg-defeasible rules"

  can-fly(x)      <=  bird(x)

  neg(can-fly(x)) <=  penguin(x)

This looks quite reasonable. However, let us now assume one slightly
different predicate assignment ("wingless" in the sense of having no
wings, which is different from the often-used "broken-wing"):

p = can-fly
q = bird
r = wingless

The "naf rule" instantiation

  can-fly(x)      <-  bird(x)  ^  naf(wingless(x))

can surely not be transformed into the "neg-defeasible rules"

  can-fly(x)      <=  bird(x)

  neg(can-fly(x)) <=  wingless(x)

because there are certainly wingless objects (e.g., rockets) that can
fly. So, already this example shows that the transformation is not valid
in general.

Xianchang Wang, Jia-Huai You, and Li Yan Yuan used a larger example to
show that the correspondence between "naf rules" and "neg-defeasible rules"
is not semantically one-to-one (see above, page 4).

In RuleML we thus keep both neg and naf, as championed by Gerd Wagner and
Benjamin Grosof (perhaps refining neutral 'not' markups into neg or naf):
http://www.mynisus.com/members/stabet/ruleml/ratioruleml2.0.html
A possible RuleML distinction of the two kinds of implication is still open.

In our above example instantiations, the difference between r = penguin and
r = wingless is that the first conjunct, q = bird, subsumes r = penguin but
has only a (small) non-empty intersection with r = wingless. On the other
hand, r = broken-wing is often understood as r = bird-with-broken-wing, so
that subsumes(q,r) would again hold.

This connection of the two conjuncts can be naturally expressed in DL with
explicit subsumption links, additionally using Anon(ymous concept nodes),
Disj(oi)nt(ness lines), and (explicit) neg(ation), graphically obtaining
(I didn't yet try to mark this up in DAML+OIL or transfer it back to RuleML):

r = penguin:
                   bird
                   /  \
                  /----\
                 /Disjnt\
                /        \   can
            penguin     Anon -----> fly
                |
       neg(can) |
fly <-----------


r = wingless:

      wingless     bird
          \        /  \
           \      /----\
            \    /Disjnt\
             \  /        \     can
             Anon1      Anon2 -----> fly
                |
       neg(can) |
fly <-----------


r = bird-with-broken-wing:

                   bird
                   /  \
                  /----\
                 /Disjnt\
        wing    /        \    can
broken <---- Anon1     Anon2 -----> fly
                |
       neg(can) |
fly <-----------


Note that a negative-fly claim is made only for penguins, wingless birds,
and birds with a wing-broken restriction, not for wingless objects.

At the end of the Dagstuhl Seminar we figured that defeasible rules deserve a
more detailed treatment, along with reaction rules, and this follow-up event
emerged:

   We will hold a workshop on Rule Markup Languages for Business Rules in the
   Semantic Web emphasizing both reaction rules (contact: Gerd Wagner) and
   defeasible rules (contact: Michael Schroeder) in conjunction with the Int'l
   Semantic Web Conference (ISWC2002) and the OntoWeb3 meeting, June 10-14,
   2002, Sardinia, Italy.

   http://tmitwww.tm.tue.nl/staff/gwagner/RuleML-BR-SW.html

Kind regards,
Harold


This archive was generated by hypermail 2.1.4 : 04/02/02 EST