RE: completeness

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
following:

  "Given two RDF graphs G1 and G2.
  Whenever G1 pD*-entails G2 by means of the model-theoretic semantic
conditions,
  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
G2,
  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"?

Cheers,
Michael

--
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