Thursday, February 16, 2006
Generative Methodology Glass Bead Games
n-articulated ontological framework
On using RDF to model biological expression
Link back to part of the “solution” to translations between
RDF / OWL and Models of Information
à- [167]
Concurrent Anticipatory web discussion à [30]
Discussion on expressiveness
Andrea:
Not taking into account the ability of OWL-Full to state that classes are also instances of other classes, in the DL fragment of OWL-Full what determines decidability is the set of concept and role constructors allowed by the logic you are using. SHOIQ(D) is decidable (and obviously SHOIN(D) is too, because it is less expressive than SHOIQ(D)). I suspect that the decision for OWL-DL to be mapped into SHOIN(D) is due to a (slightly?) better average computational behavior of SHOIN(D) reasoners with respect to SHOIQ (D) ones, but I don't know the details. Anyway, both DLs are worst- case intractable (time-exponential computational complexity or higher). Note that, even when the language is not decidable, it is not "impossible" to reason over it: just, you are not guaranteed to *always* be given an answer to your question in finite time.
To me, it would be interesting to know from experts why undecidability is never tolerated,
Reply from Ulrike
let's see: some people working on DLs indeed insist that a DL has to be decidable: this is to make sure that we do get predictable, interpretable behavior of reasoning services.
For example, if a consistency test of an ontology does not terminate -- how are we going to interpret this?
As a "yes"? "possibly"? "no"?
Anyway, you are right that, even though the reasoning problems of our DLs are decidable, they are of a complexity that might lead to rather long computations...even double exponentially long, ie, in the worst case, too long to wait for an answer.
However, we understand pretty well what is going on there, and we are able to use quite sophisticated optimizations: basically, the idea is to restrict the expressive power to that what we really want -- and then to use algorithms and optimizations that can handle these kind of statements.
This approach lets us "tune" our reasoning algorithms better.
I believe, however, that there might be cases where we would rather like to use some even more expressive power, and would accept a "semi- decision procedure" for some undecidable problem.
We should only make sure that we really need this expressive power and these costly reasoning services, and that we did not simply choose one that was "a size too large" (and too costly).
Andrea’s note continued
while intractability (non-polynomial computational complexity) seems to be. What is often said in literature, is that languages in which the satisfiability problem is intractable are accepted because, even if the worst-case computational complexity is exponential, in *most* real cases the answer can be given in a (relatively) short time. Now, why the same cannot be said about undecidable languages? Considered the fact that exponential algorithms can lead to answer times which no one will ever wait for in order to have an answer to her/his query, what is the difference between an unacceptably long answer time and an infinite answer time? In both cases, the user will stop the process.
Provided that the practical usefulness to end-users is the same for intractable and undecidable languages,
Continuing reply from Ulrike
As mentioned above, we hope that, by concentrating on intractable yet decidable DLs, we can tune our algorithms so that they behave quite well in many realistic cases: please note that all complexity results mentioned are "worst case" ones, and that the behavior of state-of- the-art DL reasoners is such that they try to be much better than the worst case...if possible.
Andrea’s note continued
I am led to think that concentrating on techniques to provide *incomplete* answers to undecidable languages (OWL-Full, for example), featuring a higher expressivity often called for in ordinary modeling, would be an extremely important research topic. But maybe I am missing something...