Re: Proposed response to Martin Merry, HP

On May 9, Jim Hendler writes:
 
[snip]

> At 15:18 +0100 5/9/03, Merry, Martin wrote:
> We wish to comment on the usefulness of OWL DL as a sensible subset of OWL
> Full.

[snip]

> In particular, we would like to see adequate practical implementation
> experience of the OWL DL constructs owl:oneOf and owl:hasValue.  We believe
> that this should include the goal that OWL DL reasoners can make a
> reasonable attempt at classic NP complete problems (such as the 3-SAT
> problem and the subgraph isomorphism problem) which can be straightforwardly
> encoded within OWL DL.  For example, any such problem that can be solved in
> seconds by a specialised reasoner should be soluble by a general OWL DL
> reasoner in minutes rather than years.

It might be worth pointing out that DL reasoners of the sort that we
are expecting to use with OWL DL have proven to be very effective at
solving 3-SAT problems, and have "won" several TANCS (TABLEAUX Non
Classical Systems) comparisons where the test data included SAT and
QBF problems.

For some reason, the encoding of SAT problems in Test [1] uses
nominals, rather than the standard class based encoding (e.g., as used
in the TANCS test suite), which pushes the problem into that part of
the language which is hard for complete reasoners to deal with. Using
the class based encoding, FaCT is able to solve the test cases in less
than 0.05s on a 1GHz PIII desktop.

Ian

[1] http://www.w3.org/2002/03owlt/editors-draft/draft/proposed-dl-500-SAT#proposed-dl-500-SAT



> 
> An alternative, would be to redefine OWL DL downwards, excluding owl:oneOf
> and owl:hasValue, which would then be subject to the health warnings of OWL
> Full - i.e. use of these constructs means that your ontology is likely to be
> outside the limits of practical reasoning. Such a redefinition of OWL DL,
> could sensibly accompany a redefinition of OWL Lite to exclude complete
> class definitions.
> 
> 
> Martin Merry
> HP Semantic Web Programme Manager
> 
> 
> 
> Martin Merry
> HP Semantic Web Programme Manager
> 
> 
> 
> -- 
> Professor James Hendler				  hendler@cs.umd.edu
> Director, Semantic Web and Agent Technologies	  301-405-2696
> Maryland Information and Network Dynamics Lab.	  301-405-6707 (Fax)
> Univ of Maryland, College Park, MD 20742	  240-731-3822 (Cell)
> http://www.cs.umd.edu/users/hendler

Received on Monday, 12 May 2003 07:32:01 UTC