Re: rule proto-proposal

From: Ian Horrocks (
Date: 05/29/01

On May 29, Peter F. Patel-Schneider writes:
> As promised (threatened), I have put together the beginnings of a proprosal
> for rules in DAML+OIL.  This is the very initial stages of a proposal, and
> has certainly not be analyzed to the extent that it should.
> peter
> 	The Beginnings of a Proposal for Rules in DAML+OIL
> WARNING:  This is not a full proposal.  I have not worked out the exact
> form of the proposal, nor have I analyzed the proposal for computational
> difficulties.
> There are many possible views on what a rule can be, ranging from
> condition-action rules as in OPS to rules of inference.  I believe that the
> latter kind of rule is most appropriate for DAML+OIL, as it maintains the
> logical flavour of the formalism.
> Thus I propose that rules of the form
> 	A -> C
> where A is the antecedant of the rule, and C is the consequent of the rule,
> be added to DAML+OIL.  The semantics of these rules would be
> 	Whenever (and however) A is true
> 	C will also be (made) true
> Therefore, both A and C have to be things that can be considered to be (or
> made) true, and would not have procedural meaning.
> So far the proposal is not very specific, only forbidding rules that have
> actions.  There are a number of possibilities for the form of A and C.  The
> least-powerful version would be have both A and C be DAML+OIL classes.
> This version of rules would not be very useful in DAML+OIL, however, as it
> can already be expressed in DAML+OIL by stating that A is a subclass of C.
> A more-powerful possibility would be to allow A to be a class expression
> with tags and allowing these tags to show up in C, which would also be
> expanded to be a collection of class expressions---not just a single class.
> In this proposal, one could do things like relating the fillers of various
> property chains to one another, something like
> 	PERSON ^ father : x ^ mother : y  -> wife-of(y,x)
> There are a number of questions concerning this proposal.
> 1/ Does it actually add any expressive power?
>    I had thought that it would, but now I am less sure of this.
> 2/ Does it capture an interesting portion of what people want to do with
>    rules?
> 3/ How hard is it to reason with?

If I understand this correctly, then it looks to me as though it both
adds expressive power and is undecidable. e.g., rules such as:

CORNER ^ inverse-vert-edge : x ^ horiz-edge : y -> diagonal(x,y)
CORNER ^ vert-edge : y ^ inverse-horiz-edge : x -> diagonal(x,y)

combined with an axiom:

CORNER -> <= 1 diagonal

would allow us to encode a grid and thus solve unconstrained tiling

It might be possible to find some sort of syntactic restriction that
prevents this (like the one that restricts the use of roles in
cardinality constraints). However, even if this were possible, I doubt
that the result would be very useful - my intuition tells me that any
useful rule extension is sure to result in undecidability. (I don't
intend this to indicate approval or disapproval of rule extensions.)

Regards, Ian

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