ontolog-forum
[Top] [All Lists]

Re: [ontolog-forum] Difference between XML and OWL

 To: "[ontolog-forum]" "Mitch Harris" Tue, 21 Oct 2008 11:35:34 -0400 <553db06d0810210835q6ce4e61ek9ace6b1b341d8af1@xxxxxxxxxxxxxx>
 ```On Tue, Oct 21, 2008 at 10:11 AM, John F. Sowa wrote:    (01) > But the most misleading point of all is the final sentence: > > > Lastly, expressiveness increases the computational costs of reasoning. > > In the Fads and Fallacies paper, I make the point that computational > complexity is *totally dependent* on the nature of the problem. > Any problem stated in a restricted language can be solved just as > fast when stated in a more expressive language.    (02) I think there is a mismatch between how people are using implicit quantifiers here.    (03) True, for any particular problem, it is in a particular complexity class or not. Its complexity (computational) does not change.    (04) But for given a set of language operators with specific meanings, the complexity of a the set of -all- problems expressible with larger selection of operators is at least as difficult (takes as long or longer) for a smaller set.    (05) For a particular problem, if you know ahead of time which complexity class it lives in, you can gear the algorithm to that. But if you don't know that about the input, a simple problem may be expressed (equivalently of course) using the larger set of operators and you may still be bound by the algorithm -needed- to deal with the larger set to do all sorts of expensive, time consuming things.    (06) Some algorithms are 'adaptive' in that they are faster for simpler inputs(less expressive; using fewer of the fancy operators), but some algorithms are not, and no matter what the input (for a given size) it runs in the same time (e.g. tableau algorithms vs automata based ones for description logics). There is no guarantee that a set of problems has an adaptive algorithm.    (07) Any problem -can- be solved as fast as it ..well... can be. But you don't know ahead of time which problem it is.    (08) Of course, just syntax checking is an extremely effective triage method. But there's no guarantee (a simple statement can be expressed badly, with lots of annoying high-complexity operators). Increasing expressiveness increases the complexity of solving the whole class.    (09) So, yes, for a specific problem, stated in a particular manner, of course adding operators to the language it is expressed in doesn't change the complexity of the original problem. But equally of course the extra operators make more problems expressible and they might take longer, and if you don't realize it, you may spend more time than necessary on the simpler problem (that doesn't actually use those new operators).    (010) Does that clarify how I think people are talking about 'expressiveness' or does it make it worse?    (011) Mitch    (012) _________________________________________________________________ Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/ Subscribe/Config: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/ Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx Shared Files: http://ontolog.cim3.net/file/ Community Wiki: http://ontolog.cim3.net/wiki/ To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx    (013) ```
 Current Thread [ontolog-forum] Difference between XML and OWL, Phani Chaitanya Re: [ontolog-forum] Difference between XML and OWL, Martin Hepp (UniBW) Re: [ontolog-forum] Difference between XML and OWL, Duane Nickull Re: [ontolog-forum] Difference between XML and OWL, Peter F Brown Re: [ontolog-forum] Difference between XML and OWL, John F. Sowa Re: [ontolog-forum] Difference between XML and OWL, Mitch Harris <= Re: [ontolog-forum] Difference between XML and OWL, Pat Hayes Re: [ontolog-forum] Difference between XML and OWL, Ed Barkmeyer Re: [ontolog-forum] Difference between XML and OWL, John F. Sowa Re: [ontolog-forum] Difference between XML and OWL, Ed Barkmeyer Re: [ontolog-forum] Difference between XML and OWL, John F. Sowa Re: [ontolog-forum] Difference between XML and OWL, Ed Barkmeyer Re: [ontolog-forum] Difference between XML and OWL, John F. Sowa Re: [ontolog-forum] Difference between XML and OWL, Ed Barkmeyer Re: [ontolog-forum] Difference between XML and OWL, John F. Sowa Re: [ontolog-forum] Difference between XML and OWL, Ed Barkmeyer