ontology-summit
[Top] [All Lists]

Re: [ontology-summit] FW: Question on DL negation [DL complexity tool]

To: <ontology-summit@xxxxxxxxxxxxxxxx>
From: "Obrst, Leo J." <lobrst@xxxxxxxxx>
Date: Mon, 5 Mar 2007 17:02:27 -0500
Message-id: <9F771CF826DE9A42B548A08D90EDEA8001A765BE@xxxxxxxxxxxxxxxxx>

John,

.Many in the community identify two kinds of complexity, as you do, sometimes called data and algorithm complexity, going back to early work by Moishe Vardi in the early 80s. I don't have wide access right now, but will provide citations soon.

However, there's excellent work in descriptive complexity that tries to gauge languages esp. logics, as I mentioned before. And this work shows there is a correlation between expressivity and algorithm, which if you think about it, must be right at some level. Given Church/Turing theorem and. Curry/Howard isomorphism, you'd expect something like this (and no, I won't go off the Chaitin deep end yet, since I think there is pragmatic value to science and math prior to the meta-math of Chaitin, and yes in general, I do agree with him).  

In addition, there has been a research thread known as knowledge compilation that addresses tranformations such as Bill Andersen's/Ontology Works set of FOL to Logic Programming transforms. In fact, these are probably the paradigmatic forms. Work by Selman and Kautz et al and Eiter/Cadoli/Donini and many others, including important work on SAT. We use this body of knowledge and techniques in our internal research addressing SW ontologies, rules, and reasoning.

The descriptive complexity folks say it comes down to the finite model property, and that even modal logic can be tractable (mostly because of restricted quantification).

Thanks,
Leo
--------------------------
Dr. Leo Obrst, MITRE, Information Semantics, lobrst@xxxxxxxxx, 703-983-6770

----- Original Message -----
From: ontology-summit-bounces@xxxxxxxxxxxxxxxx <ontology-summit-bounces@xxxxxxxxxxxxxxxx>
To: Ontology Summit 2007 Forum <ontology-summit@xxxxxxxxxxxxxxxx>
Sent: Mon Mar 05 15:40:50 2007
Subject: Re: [ontology-summit] FW: Question on DL negation [DL complexity tool]

Leo,

As I keep repeating, complexity is first and foremost a property
of an algorithm, indirectly a property of a problem, and only
very, very indirectly a property of a language:

 > This is a useful tool for determining the specific complexity
 > of the description logic you are interested in.

Most of those complexity claims are based on the assumption
that the language is going to be used to prove theorems.

But that is certainly not the case of a logic that is used to
access a database.  For example, the WHERE clause in SQL has
the expressive power of first-order logic.  But when it is
used to express a query or constraint that is evaluated against
a relational DB, the worst-case complexity takes polynomial time.

And since most relations in a database are indexed on the key
field or fields, many queries and constraints can be evaluated
in logarithmic time.

When talking about complexity, it is essential to keep the purpose
in mind.  People keep saying that language L is efficient or
inefficient without ever mentioning the all-important question:

     Efficient for what purpose?????

John


_________________________________________________________________
Msg Archives: http://ontolog.cim3.net/forum/ontology-summit/
Subscribe/Config: http://ontolog.cim3.net/mailman/listinfo/ontology-summit/ 
Unsubscribe: mailto:ontology-summit-leave@xxxxxxxxxxxxxxxx
Community Files: http://ontolog.cim3.net/file/work/OntologySummit2007/
Community Wiki: http://ontolog.cim3.net/cgi-bin/wiki.pl?OntologySummit2007
Community Portal: http://ontolog.cim3.net/


_________________________________________________________________
Msg Archives: http://ontolog.cim3.net/forum/ontology-summit/ 
Subscribe/Config: http://ontolog.cim3.net/mailman/listinfo/ontology-summit/  
Unsubscribe: mailto:ontology-summit-leave@xxxxxxxxxxxxxxxx
Community Files: http://ontolog.cim3.net/file/work/OntologySummit2007/
Community Wiki: http://ontolog.cim3.net/cgi-bin/wiki.pl?OntologySummit2007
Community Portal: http://ontolog.cim3.net/    (01)
<Prev in Thread] Current Thread [Next in Thread>
  • Re: [ontology-summit] FW: Question on DL negation [DL complexity tool], Obrst, Leo J. <=