W3C home > Mailing lists > Public > public-owl-wg@w3.org > February 2008

RE: completeness

From: Michael Schneider <schneid@fzi.de>
Date: Fri, 22 Feb 2008 16:56:20 +0100
Message-ID: <0EF30CAA69519C4CB91D01481AEA06A075104C@judith.fzi.de>
To: "Peter F. Patel-Schneider" <pfps@research.bell-labs.com>
Cc: <public-owl-wg@w3.org>
Hi Peter

Peter F. Patel-Schneider wrote: 

>> Alan,
>> In terms of "completeness," I think pD* rules are complete 
>(correct me
>> if I am wrong on this please). 
>Not quite.  The pD* rules need an auxiliary test for contradictions.
>They could probably be made refutation complete.

Hm, I'm not sure whether I understand this.

There are of course at least two notions of "completeness" around here. One
is the completeness of the triple rules w.r.t. the model-theoretic semantic
conditions. The other one is regarding how much of this rule corpus is
actually implemented. I will distinguish between these notions by "ruleset
completeness" vs. "implementation completeness". But I do not see how any of
these two notions matches the "contradiction test" case you mention.

For the "ruleset completeness" case, to my understanding this means the

  "Given two RDF graphs G1 and G2.
  Whenever G1 pD*-entails G2 by means of the model-theoretic semantic
  then there exists a finite sequence of rule applications which lead from
G1 to G2."

For the "implementation completeness" case, I think this means for a
specific reasoner:

  "Given two RDF graphs G1 and G2:
  If there is a finite sequence of rule applications which lead from G1 to
  then the reasoner says 'yes'."

I do not see where the contradictions come into play here. I can, of course,
ask for a special graph G2* which encodes some contradiction in triple form,
and ask if another graph G1* entails G2*, e.g:

  G2* := {
    x owl:sameAs y
    x owl:differentFrom y

Do you mean that for pD* there are two such graphs G1* and G2*, where G1*
entails G2* model-theoretically, but there is no respective rule-sequence?
Or that for each reasoner there exist such two counter-example graphs on
which the reasoner fails to recognize the entailment?

Btw: What is meant by the term "refutation complete"?


Dipl.-Inform. Michael Schneider
FZI Forschungszentrum Informatik Karlsruhe
Abtl. Information Process Engineering (IPE)
Tel  : +49-721-9654-726
Fax  : +49-721-9654-727
Email: Michael.Schneider@fzi.de
Web  : http://www.fzi.de/ipe/eng/mitarbeiter.php?id=555

FZI Forschungszentrum Informatik an der Universität Karlsruhe
Haid-und-Neu-Str. 10-14, D-76131 Karlsruhe
Tel.: +49-721-9654-0, Fax: +49-721-9654-959
Stiftung des bürgerlichen Rechts
Az: 14-0563.1 Regierungspräsidium Karlsruhe
Vorstand: Rüdiger Dillmann, Michael Flor, Jivka Ovtcharova, Rudi Studer
Vorsitzender des Kuratoriums: Ministerialdirigent Günther Leßnerkraus

Received on Friday, 22 February 2008 15:56:34 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 6 January 2015 21:42:02 UTC