Re: [ontolog-forum] Webby objects

[William Frank <williamf.frank@xxxxxxxxx>]

I too do not understand what 'computationally complete' could mean, aside from decideable. 

There are two different senses of 'completeness' in the worlds of logic and model theory.

1. a LOGIC L consisting of a language, L, a deductive system D, and a theory of valid entailment E, 

is complete 

iff every valid consequence according to E can be proved by a correct deduction in D.

(the 'weak completeness' variation on this is not useful for much).


2. an AXIOMATIC THEORY T, with axioms A, expressed in language L of the  logic L

is complete 

iff for every statement S in language L 

S is a valid consequence of the axioms A, 

or 

(not S) is a valid consequence of the axioms A


Mixing these up has lead to several miscommunications in this forum.

The are often mixed up because so many lesser teachers of mathematics and computer science adopt the formalist school in which logical theories are not distinquished from the mathematical and scientific theories that can be built on them; they are all  'just' 'formal systems'.   Fortunately, that stance is not practical in ontology work, which all depends on having a knowledge representation scheme (a logic L) before we make any ontological statements in L. 

one might use the _expression_ 'deductively complete' to make clear that one was talking about the completeness of a logic, focussed as it is on the logics deductive system. 



Wm

On Mon, Jan 7, 2013 at 7:17 AM, Michael Brunnbauer <brunni@xxxxxxxxxxxx> wrote:

Hello Pat,

sorry for the late answer - I was quite busy.

On Sun, Nov 18, 2012 at 04:06:51PM -0800, Pat Hayes wrote:
[MB]
> > I am confused by the Wikipedia article about OWL:
> >
> > https://en.wikipedia.org/wiki/Web_Ontology_Language#OWL_DL
> >
> > It says that "OWL DL was designed to provide the maximum expressiveness
> > possible while retaining computational completeness (either phi or not phi
> > belong), decidability (there is an effective procedure to determine whether
> > phi is derivable or not)".
> >
> > The statement about computational completeness of OWL DL is wrong, isn't it ?
>
> I had a *huge* fight with the DL people (mostly Ian Horrocks) about this. Ian's view is that logics that aren't decideable are simply faulty, broken, inadequate, not of interest, etc.. Any "reasonable" logic should be decideable. So, he simply *assumes* decideability as a basic property of a logic. OK, that settled, we turn to completeness. If the logic is decideable, then one can phrase completeness as there being an effective procedure to determine entailment.

Doesn't decidability already imply this by definition ? http://en.wikipedia.org/wiki/Decidability_%28logic%29 suggests this to me.

I do not have a clue what the term "computational completeness" in

 https://en.wikipedia.org/wiki/Web_Ontology_Language#OWL_DL

means. The word "completeness" links to the article about complete theories
and the addition "(either phi or not phi belong)" also suggests this sense.
But surely, OWL DL does allow incomplete theories.

Regards,

Michael Brunnbauer

--
++  Michael Brunnbauer
++  netEstate GmbH
++  Geisenhausener Straße 11a
++  81379 München
++  Tel +49 89 32 19 77 80
++  Fax +49 89 32 19 77 89
++  E-Mail brunni@xxxxxxxxxxxx
++  http://www.netestate.de/
++
++  Sitz: München, HRB Nr.142452 (Handelsregister B München)
++  USt-IdNr. DE221033342
++  Geschäftsführer: Michael Brunnbauer, Franz Brunnbauer
++  Prokurist: Dipl. Kfm. (Univ.) Markus Hendel

_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/
To join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J

-- 
William Frank

413/376-8167


_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/  
Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/  
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/ 
To join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J    (01)