On 8/11/2010 6:16 PM, Pat Hayes wrote:
> Or (just to keep the record clear) another option is to simply abandon
> this quest to achieve decidability, and work with semi-decidable
> complete logics such as classical FOL. (01)
Yes, and some groups, including Cyc and VivoMind, go a bit farther: (02)
1. Note that the complexity class (including P, NP, or undecidable) is
*not* a property of a logic, but of problems stated in the logic. (03)
2. If you use a very expressive logic, you are not required to use
all possible features of that logic in every problem. (04)
3. Instead, you can use a variety of inference engines optimized
for different subsets. (In the case of Cyc, they have about
three dozen different inference engines optimized for various
subsets of CycL.) (05)
4. For all the common cases and many rare cases, it is possible
to perform a quick syntactic check to determine the complexity
class of the given problem. Then assign the problem to an
appropriate inference engine (or sometimes different engines
for different aspects of a complex problem). (06)
5. For most cases, it is possible to give the user a guarantee
of performance on a particular problem (if it is an easy one)
or a warning (if it is a hard one). For those rare cases,
where the complexity class cannot be determined, it is also
possible to say that as part of the warning. (07)
> As Ian points out in another message in this thread, this means that
> one cannot then undertake to offer users a universal *guarantee* of
> performance (08)
True, but Cyc could also provide a guarantee for most if not all
the cases for which an OWL reasoner can provide a guarantee. But
Cyc can also offer to do its best effort on those problems for
which a guarantee is not possible. (09)
As that article on the issue of P=NP points out, many problems,
such as graph isomorphism (GI), that may take exponential time
have a huge number of efficient special cases. For example,
the *only* cases for which GI takes exponential time are ones
where the upper bound on the branching factor of the graph is
O(n) -- i.e., the number of links to any node is proportional
to the total number n of nodes in the graph. (010)
For conceptual graphs and even RDF graphs, the branching factor
is almost never O(n). It's usually bounded by a constant or
at worst by a polynomial in (log n). (011)
> In our case, it would mean that all this plethora of multiple
> standards and notations (RDFS, OWL, OWL2, RIF, RuleML, WhatNextML...)
> could be simply described as being what they in fact are, which is
> various subsets of classical FO logic, or of ISO Common Logic. One
> parser could handle all of them, all expressed in a single notation,
> and the work of re-designing a syntax and a new semantics, and writing
> a bundle of close-to-unreadable specification documents would not have
> to be re-done every few years. (012)
Certainly. That's what Cyc does. They have been able to handle a
huge range of options by implementing different inference engines.
But the users and SMEs don't have to worry about (or even know about)
the complexity classes or the inference engines. For most cases,
even the knowledge engineers don't have to worry, except in the
unusual cases where they have to add another inference engine or
revise the tests for choosing which inference engine to use. (013)
For many problems, it's also possible to write a static analyzer
and compiler that extracts axioms from Cyc and translates them
to an optimized form for inference engines outside of Cyc.
See, for example, the approach that Bill Andersen and his
buddies implemented. I discuss that on p. 6 of the following: (014)
http://www.jfsowa.com/pubs/fflogic.pdf
Fads and fallacies about logic (015)
John (016)
_________________________________________________________________
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
To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx (017)