- From: Peter F. Patel-Schneider <pfps@research.bell-labs.com>
- Date: Tue, 03 Oct 2006 12:27:54 -0400 (EDT)
- To: fukushige.yoshio@jp.panasonic.com
- Cc: semantic-web@w3.org
[I'm replying directly to the initial message instead of including some of the replies, but I will address some of the information there as well.] OWL FULL is undecidable (as stated by Pierre-Antoine Champin this is an imprecise gloss of something like "entailment in OWL Full is undecidable") for a number of reasons. One of these comes from the Description Logic used in OWL Full. Another comes from RDF(S). More formally, there is no way of building a machine that correctly and always and finitely answers questions like: Does an OWL ontology (i.e., an RDF document) imply (in the OWL Full semantics) that one class is a subclass of another? The "question" can be one of many similar questions, including whether an OWL ontology is consistent and an individual is a member of a class. I don't like the wording in the initial message for several reasons, including the unusual use of "system". It is much better to say something like There are many OWL Full ontologies that are "decidable" - i.e., any question of interest to that ontology can be answered. This includes all OWL Full ontologies that don't mention any OWL vocabulary. Note that it is possible to ask undecidable questions about most OWL ontologies. Consider an empty ontology and asking questions that use complex OWL descriptions instead of just names of classes in the ontology. This is an undecidable problem. Note also that given any particular OWL Full ontology *is* possible to build a machine that correctly answers all questions like Is class A a subclass of class B. where A and B are classes mentioned in the ontology. Why? Because there are only a finite number of such questions and thus this can simply be done by table lookup. Now it is *not* possible to build this table in general, but for any particular ontology the table does exist and thus there is some machine that can do the right thing. (Yes, this is being a bit pedantic, but one does have to be careful to state things correctly when talking about decidability and related issues.) I recommend reading the paper Boris Motik On the Properties of Metamodeling in OWL ISWC2005 http://www.cs.man.ac.uk/~bmotik/publications/papers/motik05metamodeling.pdf as it has a discussion of some of the sources of undecidability in OWL Full. Peter F. Patel-Schneider Bell Labs Research PS: It is the case that any RDF document has a formal meaning in OWL Full (i.e., the RDF compatiable semantics in http://www.w3.org/TR/owl-semantics/rdfs.html). However this formal meaning may be rather strange for RDF documents that do unusual things. The example in the message from Pierre-Antoine Champin is actually a very benign example - one where there actually is a fairly intuitive semantics. From: "Yoshio Fukushige" <fukushige.yoshio@jp.panasonic.com> Subject: Readings on OWL's (un)decidability? Date: Mon, 2 Oct 2006 01:27:15 -0500 > > Hello, > > I've seen many documents saying "OWL FULL is undecidable" ... (a) > > But which of the following does (a) mean?: > > (1) "There is no system which is decidable where there is a Class, say > ClassA, > that is an instance of another Class." > > or > > (2)"There is at least one system which is undecidable where/because > there is a Class, say ClassA, > that is an instance of another Class. > i.e. Not every system with a vocabulary in OWL FULL is decidable." > > What do you recommend me to read for the proof of (a)? > (A (short) article on the Web is preferred to a whole book ^_^;) > > Best, > Yoshio > > -- > Yoshio Fukushige <fukushige.yoshio@jp.panasonic.com> > Network Development Center, > Matsushita Electric Industrial Co., Ltd. > >
Received on Tuesday, 3 October 2006 16:28:17 UTC