Decidability v. complexirty (was RE: Proposed response to Martin Merry, HP)

Jeremy - I'll take one more stab,and if that doesn't work, I'll give 
up and we'll just rely on process eventually working out something 
that makes sense

CHAIR HAT OFF

At 4:01 PM +0200 6/13/03, Jeremy Carroll wrote:
>>
>>  Jeremy - that's simply not true - there are people who have
>>  implemented every feature in combination - I'm not sure what more
>>  than that you can mean by a "research hypothesis" -- I think you're
>>  just misunderstanding the situation or else I simply don't understand
>>  you.  However, for every test case you've proposed we seem to have
>>  people who think they can implement it - so I have no clue what you
>>  mean by a "theoretical construct"
>>    -JH
>>
>
>I am not sure what to make of this either - I may have misunderstood the
>situation or you may have done or we may have different concerns.

I suspect those are not XORs...

>
>We struck the concept of a "complete DL consistency checker" on the grounds
>that we did not think there would be one.

No, that is not why WE (you and me both) struck it, I voted to remove 
it because I still believe we should remove all the conformance 
clauses, and I was happy to remove this one (and will be happy to 
remove the OWL Lite one as well if the issue were to get opened).

I will admit that at the time we held that vote I did not believe 
there existed an implementation that could handle both oneOf and 
InverseOf at the same time.  I have now seen two of these, one of 
which is commercially viable, therefore if the vote were held again I 
would probably abstain rather than vote to strike.

>
>So for Lite we already have (I believe) complete consistency checkers, for
>Full we know that there cannot be such things, and for DL we believe these
>not to be commercially practical.

WE do not.  YOU do.  I believe the above is an incorrect statement

>I think that this is sufficiently relevant
>to the new user trying to work out how to get into OWL to make it in to the
>Guide in some way, and don't find the text as proposed as spelling out these
>different levels of practical reasoning adequately.

but I have no idea of what you mean by practical reasoning (and 
"adequately") - with enough instance data, for example, even a 
polynomial algorithm would be inadequate.  With the current state of 
the world, I think the systems that exist are more than adequate, and 
some are in use at the present time working just fine.
  If you will define a metric and a performance goal, then we can 
evaluate this argument -- if you say "all problems in finite time" 
then I win -- if you say "all problems in less than 1200 seconds" 
then you win (but then we must also remove the clause for OWL Lite, 
and for everything else on the computer, for that matter
   (note - to type out all numbers from 0 to 144! will not terminate 
in our lifetimes even assuming we live to be 200 and Moores law 
continues that whole time and the computation runs on the fastest 
computer available at any given moment (in fact, on every available 
computer in parallel at any moment - 10^245 is a staggeringly huge 
number)).


>
>i.e. if you confine yourself to OWL Lite then hopefully you can take your
>data from one OWL Lite system with a complete reasoner to another without
>major rework.

and why would this be different for DL - that is where you seem to go 
off into lala land

>
>If you confine yourself to OWL DL then such portability is less expected -
>while all DL features may be implemented we do not expect an implementation
>of all of them all at the same time, (at least not "complete").

Again, you say WE but I haven't heard any developer agree - and, in 
fact, I've heard two developers disagree (and prove it by having 
implementations which handle every feature at the same time).

>
>In OWL Full then expect less portability than that.
>

I definitely disagree with that - I expect OWL Full to be more 
portable than Lite, because I don't have to worry about the 
restrictions to the FOL set of RDF.   I also expect reasoners like 
Jos' to do far better, in practice, on Full than you seem willing to 
believe - time will see which one of us is wrong (but if you're 
willing to put money down, I'll take it).

>However, on the plus side, even in Full any reasoning a conformant OWL
>reasoner does will be consistent with any other reasoning a different
>conformant OWL reasoner has done.
>

exactly, and I think that is a very large set compared to what you do.

So, summarizing:
  We agree about Lite.
  You are wrong about DL.
  We agree about Full.

So I'm comfortable that process will succeed...

  -JH


>Jeremy

CHAIR HAT, SLIGHTLY BRUISED, BACK ON HEAD.

-- 
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-277-3388 (Cell)
http://www.cs.umd.edu/users/hendler      *** NOTE CHANGED CELL NUMBER ***

Received on Friday, 13 June 2003 17:17:07 UTC