- From: Michael Schneider <schneid@fzi.de>
- Date: Sat, 4 Sep 2010 15:01:20 +0200
- 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, Michael -- 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