Tests in responses to LC comments on DL design

During my discussions with people at WWW it became clear to me that 
some of our comments had come from people who were confused a bit 
about the issues of decidability v. run-time complexity.  I think it 
might help if we had a test case that showed that a document which 
contained both inverse and oneOf is not necessarily going to make the 
system fall to its knees (i.e. theoretically we know there exist 
problems that can be encoded in OWL DL, using these constructs, that 
would take a very long time to run - but in practice these don't come 
up that often and using some sort of resource bounds is done in every 
practical implementation that I know of).
  I wonder if adding a test of something like the following might help 
(forgive me for sketch, rather than details, thought it would be 
easier for people to read, and avoid my having to run this email 
through Sean's DL checker :->)

TEST 1: Consistency check - the following is consistent

Define a class called Continent as oneOf (Asia Europe NorthAmerica ...)

Define a class called Country

Define ContainsLocation as an objectProperty
      with domain of Continent and range of Country

Define ContainedIn as the inverseOf ContainsLocation

<:Finland owl:class :Country>
<:Finland :ContainedIn :Europe>

Test 2: Not consistent

same as above but assert

<:Finland owl:class :Country>
<:Finland :ContainedIn :NorthernHemisphere>

===========
These would show that this kind of reasoning doesn't automatically 
break DL, and would also show that there are useful (or at least 
evocative) examples where you see that the use of both inverse and 
oneOf can be helpful.

I also thought about proposing a test that would be a challenging 
combination of inverseOf and OneOf (where an exhaustive enumeration 
over a very large set would be needed), but I'm not a good enough 
logician to come up with an example that would be very hard but 
wouldn't need to include some extremely large set of instances  - 
maybe a better logician than I could design a more subtle test that 
wouldn't need lots of pages to write down.



-- 
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 Thursday, 29 May 2003 08:06:44 UTC