W3C home > Mailing lists > Public > semantic-web@w3.org > September 2010


From: Michael Schneider <schneid@fzi.de>
Date: Sat, 4 Sep 2010 15:01:20 +0200
Message-ID: <0EF30CAA69519C4CB91D01481AEA06A002117489@judith.fzi.de>
To: "Cristiano Longo" <longo@dmi.unict.it>
Cc: <semantic-web@w3.org>, "Domenico Cantone" <cantone@dmi.unict.it>
Cristiano Longo wrote on September 03:

>Dear all, I wonder which if there is some restriction of OWL Full that
>have been found to be decidable (obviously excluding OWL-DL).

Semantic or syntactic restrictions?

Semantic restrictions: RDFS, pD*, and the OWL 2 RL/RDF rules.

Syntactic restrictions: Keep the semantics of OWL Full as is, but restrict
the set of valid OWL Full ontologies (i.e., RDF graphs) to those with size
at most N, where N is some natural number constant, and where the size of an
OWL Full ontology is defined to be the smallest number of bits for which
there is an RDF/XML document that serializes the ontology. Let's call this
language "OWL-Full_N". Now, for example, consistency checking is clearly
decidable for OWL-Full_N, since there is only a finite (<=2^N) number of
possible OWL-Full_N ontologies, and thus there exists a finite lookup table
that maps all these ontologies to their respective consistency result
(either true or false). The lookup table can, for example, be implemented as
a binary search tree of depth N (highly tractable!). Note that N can be any
number, for example one Million, or one Billion, or the number of nuclear
particles in the Milky Way. Only in the limit case, for lim N -> oo,
undecidability eventually pops up again. So it should be possible to find a
suitable decidable fragment of OWL Full that covers all of today's and all
future practical applications. :-)

Only half joking,

Dipl.-Inform. Michael Schneider
Research Scientist, Information Process Engineering (IPE)
Tel  : +49-721-9654-726
Fax  : +49-721-9654-727
Email: michael.schneider@fzi.de
WWW  : http://www.fzi.de/michael.schneider
FZI Forschungszentrum Informatik an der Universität Karlsruhe
Haid-und-Neu-Str. 10-14, D-76131 Karlsruhe
Tel.: +49-721-9654-0, Fax: +49-721-9654-959
Stiftung des bürgerlichen Rechts, Az 14-0563.1, RP Karlsruhe
Vorstand: Prof. Dr.-Ing. Rüdiger Dillmann, Dipl. Wi.-Ing. Michael Flor,
Prof. Dr. Dr. h.c. Wolffried Stucky, Prof. Dr. Rudi Studer
Vorsitzender des Kuratoriums: Ministerialdirigent Günther Leßnerkraus
Received on Saturday, 4 September 2010 13:01:57 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 1 March 2016 07:42:22 UTC