On 12/29/2012 6:41 AM, John F Sowa wrote:
>> >The trouble I see in such publications by influential members of
>> >the W3C is that one particular formalism—DL—is being confused with
>> >the general issue of formal representation and use of ontologies.
> Not only that, OWL's major features are useless. To prove that their
> algorithms are decidable, they constrain all models to trees. That
> constraint rules out benzene rings (a huge part of organic chemistry
> and pharmaceuticals). It also rules out the metal or wood structures
> of buildings, bridges, and airplane wings, which contain linked
> triangles for rigidity. And forget about electronic devices --
> they all contain*circuits*.
>
> But the size and computational complexity of trees grow
> exponentially with depth. Most programmers don't understand
> decidability, but they certainly know that exponential algorithms
> don't scale. Decidability just means finite computing time --
> even though that time may be longer than the age of the universe. (01)
Indeed - this is what I explain in the paper I cited (Aďt-Kaci, H.,
Description logic vs. order-sorted feature logic. In Proceedings of the
20th International Workshop on Description Logics. Lecture Notes in
Computer Science. Springer-Verlag, 2007.
http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-250/paper_2.pdf). (02)
I quote from that paper, page 5: (03)
"On the other hand, constraint-propagation rules based on Deductive
Tableau methods such as used in [OWL] or shown in Fig. 1 [...] proceed
bottom-up by building larger and larger constraint sets by completing
them with additional (and often redundant) constraints. In short,
OSF-constraint normalization follows a reductive semantics (it
eliminates constraints) while DL-constraint propagation follows an
inflationary semantics (it introduces constraints). As a result, DL’s
tableau-style reasoning method is expansive - therefore, expensive in
time and space. One can easily see this simply by realizing that each
rule in Fig. 1 builds a larger set S as it keeps adding more constraints
and more variables to S. [...] Finally, it requires that the
constraint-solving process be decidable. By contrast, the OSF
labelled-graph unification-style reasoning method is more efficient both
in time and space. Moreover, it can accommodate semi-decidable - i.e.,
undecidable, though recursively enumerable - constraint-solving." (04)
I also make this point explicit on slides 69 and 86 of my talk "A
Sorted-Graph Unification Approach to the Semantic Web" -
http://www.hassan-ait-kaci.net/pdf/osf4sw.pdf (keynote pres. @ WI-IAT
2011 - http://wi-iat-2011.org/- see abstract at
http://www.wi-iat-2011.org/ressources/speakers/presKaci.pdf) (05)
OSF constraint logic not only accommodates multiple inheritance from the
start (by graph *unification* computing the *GLB* of two sorted graphs),
it does so using scalable modulated sort encoding that yields
quasi-constant time sort (or "concept") intersection, which scale up
with only logarithmic space and time complexity [Hassan Ait-Kaci, Robert
Boyer, Patrick Lincoln, Roger Nasr, "Efficient Implementation of Lattice
Operations," ACM Transactions on Programming Languages and Systems,
11(1), pp. 115–146, January 1989.
(http://www.hassan-ait-kaci.net/pdf/encoding-toplas-89.pdf)]. (06)
-hak
--
http://www.hassan-ait-kaci.net/contactme.html (07)
hak.vcf
Description: Vcard
_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
Config Subscr: 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 join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J (01)
|