W3C home > Mailing lists > Public > public-owl-wg@w3.org > November 2007

ISSUE-5: n-ary datatypes -decidability - datatype group?

From: Jeremy Carroll <jjc@hpl.hp.com>
Date: Mon, 12 Nov 2007 20:08:07 +0000
Message-ID: <4738B2A7.6080401@hpl.hp.com>
To: public-owl-wg@w3.org


3) no design for determining how to ensure decidability
    (maybe Jeff Pan's design?)

It is important in OWL DL that the reasoning task is strongly decidable.

(Personally I don't find this a compelling feature of OWL DL, but I 
understand that it is an unbudging design criterion)

With n-ary datatypes it appears to be possible to describe arithmetic 
relationships, built using addition, mutliplication and inequalities.

In XML Schema Datatypes as supported by OWL 1.0, it is possible to 
describe unbounded integers amongst other types.

Thus with n-ary datatypes it appears to be possible to construct 
arbitrary diophantine equations, and Hilbert's tenth problem then tells 
us that we need to consider how to ensure decidability.
(This argument is spelt out in greater detail in the Turner and Carroll 
technical report).

Jeff Pan, both in his thesis, and in the Pan and Horrocks paper, is 
aware of this issue, and provides a design called datatype groups which 
is motivated by trying to ensure decidability of the description logic 
reasoner, with a clean modular interface to a datatype reasoner, that 
deals with the numeric problems.

This work is not used, or referenced, by the member submission design, 
which hence seems to loose decidability - this may also help to explain 
why there are no implementations.


References
==========

Pan PhD
http://dl-web.man.ac.uk/thesis8.php

Pan and Horrocks
Jeff Z. Pan and Ian Horrocks. Web ontology reasoning with datatype 
groups. In Dieter Fensel, Katia Sycara, and John Mylopoulos, editors, 
Proc. of the 2003 International Semantic Web Conference (ISWC 2003), 
number 2870 in Lecture Notes in Computer Science, pages 47-63. Springer, 
2003.

Turner and Carroll
http://www.hpl.hp.com/techreports/2007/HPL-2007-37.html
Received on Monday, 12 November 2007 20:08:36 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 8 January 2008 14:13:27 GMT