Re: Limited complexity requirement?

At 20:39 +0200 7/15/04, Enrico Franconi wrote:
>On 15 Jul 2004, at 20:30, Jim Hendler wrote:
>>  We would aim for the opposite - ease in design and implementation, 
>>as opposed to guarantee of efficient computation (which, given the 
>>expressivity of RDF we provably could not gaurantee without putting 
>>new restrictions on the RDF graphs)
>
>Jim, can you better explain this statement on RDF? I thought 
>everything is worst case polynomial in RDF(S).
>cheers
>--e.

Enrico-
  First, I'm pretty sure I remember that graph algorithms on cyclic, 
labeled pseudo graphs include some semidecidable things, but I could 
be wrong.
  More importantly, however, don't forget that RDF actually allows for 
RDF statements that change the semantics of RDF itself.  For example, 
I can have a document that reads
  rdfs:class rdfs:subClassOf rdfs:subClassOf.
and I'm suspecting that any language that allows such 
self-modification must allow me to do some really nasty stuff.  I 
could be wrong, to be honest I have studied the RDF/S model theories 
well enough to know if anyone has put in things to prohibit creating 
nasty situations, so I apologize if I am wrong... but it is hard for 
me to imagine that a query language querying a graph that could have 
been modified in relatively arbitrary ways wouldn't have potential 
problems.  I also recall that one of the differences between OWL DL 
and OWL Full was putting in some restrictions to prevent some of the 
RDF things that caused undecidability...  but I'm not the expert on 
this stuff, Peter Patel-Schneider and Ian Horrocks were the ones who 
had the most decidability issues (note that technically we are 
talking semi-decidability) -- it's also possible that the problems 
were coming from the extra expressiveness of the OWL over the RDFS 
so, again, I could be wrong.
  -JH

-- 
Professor James Hendler			  http://www.cs.umd.edu/users/hendler
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)

Received on Thursday, 15 July 2004 17:00:15 UTC