W3C home > Mailing lists > Public > www-rdf-logic@w3.org > June 2001

Re: DAML-S expressiveness challenge #1

From: Deborah Mcguinness <dlm@ksl.stanford.edu>
Date: Mon, 18 Jun 2001 10:18:58 -0700
Message-ID: <3B2E3802.A1F941B6@ksl.stanford.edu>
To: Tim Finin <finin@cs.umbc.edu>
CC: David Martin <martin@AI.SRI.COM>, www-rdf-logic@w3.org
I thought I might add a little emphasis to a point in this discussion on
attribute vs. role chains.

Note that alex borgida's example that tim finin refers to mentions
"attribute chains"  i.e. these all have cardinality maximum restrictions of
1.
we found in classic that adding these equality (or "same-as") restrictions
to classic was extremely useful.
Alex also took the lead on finding that adding equality restrictions on
general role chains - i.e. where at least one role in the role chain does
NOT have a maximum cardinality of 1 - is hard.  He and Peter Patel-Schneider
wrote a paper in 1994 on the semantics of classic that has more details.
Borgida, A., & Patel-Schneider, P. F. (1994). A semantics and complete
algorithm for sub-
sumption in the classic description logic. Journal of Arti cial Intelligence
Research,
1, 277{308.

to refer in the paper tim mentioned, alex points out on page 415-416:
"A second kind of construct that is dicult to add eciently and completely
is same-as.
The reason here is that same-as interacts with all in a way that generates a
potentially in-
nite number of all restrictions; therefore, the implementation of same-as is
best combin
with that of all, resulting in a non-tree data structure (Borgida &
Patel-Schneider, 1994).
A speculative way to preserve structural subsumption might be to allow all
to apply to
chains of a attributes represented by regular expressions. (In general, the
complications of
implementing same-as are the reason it does not appear in C-classic and
neo-classic.)"


Deborah

Tim Finin wrote:

> > From: www-rdf-logic-request@w3.org on Behalf Of David Martin
> > Sent: Thursday, June 14, 2001 5:29 PM
> > ...
> > (1) Can the DESIRED CONSTRAINT be expressed in DAML+OIL, and if not,
> > is it likely that DAML+OIL will evolve to allow its expression?
>
> I recall that versions of KL-ONE had various kinds of
> constraints that could span roles and role chains.  The equality
> constraint was the one in the example used to explain the general
> feature.  I think I've seen this in lots of KR languages in the DL
> family.  A quick search on the web to refresh my memory revealed a
> paper by Alex Borgida I had not previously seen:
>
>   Extensible Knowledge Representation: the Case of Description Reasoners
>   JAIR 10 (1999) 299-434.
>   http://www.cs.washington.edu/research/jair/abstracts/borgida99a.html
>
> which discusses the utility of adding an equality constraint which
> holds between two role chains as well as the difficulties in adding
> this to a KR language.  In fact, he motivates this by the problem of
> describing actions and subactions:
>
>   Let us consider the extensions needed for a rather complex new concept
>   constructor: same-as. The semantics of same-as([f1...fn],[g1...gm]),
>   as introduced earlier, is that it denotes individuals for which
>   the two attribute chains [f1...fn] and [g1...gm] have the same
>   known filler. (The attributes must each have exactly one filler.)
>   This constructor is very useful in representing the relationship
>   between actions and subactions.
>
> Of course, I'm not sure what the consequences would be of
> adding this to DAML+OIL.  I'm sure it would make some operations
> (e.g., subsumption) *much* more difficult. But, it *is* an extremely
> useful feature from a modelers point of view.

--
 Deborah L. McGuinness
 Knowledge Systems Laboratory
 Gates Computer Science Building, 2A Room 241
 Stanford University, Stanford, CA 94305-9020
 email: dlm@ksl.stanford.edu
 URL: http://ksl.stanford.edu/people/dlm/index.html
 (voice) 650 723 9770    (stanford fax) 650 725 5850   (computer fax)  801
705 0941
Received on Monday, 18 June 2001 13:18:54 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Monday, 7 December 2009 10:52:40 GMT