[Top] [All Lists]

Re: [ontolog-forum] Planning another NIST-Ontolog joint event for April

To: "[ontolog-forum]" <ontolog-forum@xxxxxxxxxxxxxxxx>
From: Christopher Menzel <cmenzel@xxxxxxxx>
Date: Fri, 8 Dec 2006 11:47:40 -0600
Message-id: <F0221C30-2FCE-4C7C-BCE3-06E1EFD51AB1@xxxxxxxx>
On Dec 8, 2006, at 9:02 AM, Steve Ray wrote:
> ...
> How about:
>                       Semantic Mapping
>                            or
>               How we must learn to love heterogeneity
> Given that we will always be in a world where multiple ontologies  
> coexist, what
> choices do we have for mapping, or linking, concepts among these  
> ontologies?
> Must we be content with simply having humans assert semantic  
> equivalence?
> If so, what hope is there for automated integration? Is there  
> potential in using
> pattern-matching algorithms? Is is realistic to believe that  
> reasoning systems
> will be able to discover and/or prove semantic equivalence between  
> concepts in
> different ontologies?    (01)

Hi Steve, nice questions.  I think there are good grounds for  
optimism about the development of tools to *support* semantic  
mapping, but (as has been noted numerous times in various forums,  
workshops, and conferences) I think it is also important to bear a  
critical theoretical fact in mind:  it is mathematically impossible  
*in general* to prove that two propositions (equivalently, two  
concepts) are semantically equivalent.  Proving the semantic  
equivalence of two  propositions means (at least) proving that they  
are logically equivalent and that general problem is not only  
computationally intractable, it is flat out undecidable: there is no  
algorithm, even a massively inefficient one, that can, for any two  
arbitrary propositions, determine whether or not they are logically  
equivalent.  (There is an algorithm that will, eventually, tell you  
if they *are* in fact equivalent; but there is no algorithm that can  
guarantee an answer if they aren't.)    (02)

That said, it should be emphasized that this result is typically  
proven with respect to full-first order languages, which is why,  
e.g., the OWL developers modeled OWL (Lite and DL) on description  
logics, which give up some of the expressive power of full first- 
order logic in order to regain decidability.  Thus, questions of  
semantic equivalence expressed in OWL (Lite and DL -- OWL Full is  
provably undecidable) are theoretically decidable.  This is obviously  
the crucial theoretical trade-off: expressiveness for tractability/ 
decidability.  And the crucial question is whether a semantic mapping  
environment possessing the latter has given up so much of the former  
as to render it largely impotent vis-a-vis the task for which it was  
designed.  Notably, how serious are the expressive limitations of OWL  
as a semantic mapping environment?  I have no firm opinion on this  
latter question (I am in fact rather impressed by how much one *can*  
represent in OWL-DL), and raise it only for discussion purposes.    (03)

Chris Menzel    (04)

Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/  
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/ 
To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx    (05)

<Prev in Thread] Current Thread [Next in Thread>