[Top] [All Lists]

[ontolog-forum] Logic Interchange Gotchas (Was: owl2 and cycL/cycML)

To: "[ontolog-forum]" <ontolog-forum@xxxxxxxxxxxxxxxx>
From: Adrian Walker <adriandwalker@xxxxxxxxx>
Date: Thu, 12 Aug 2010 15:26:40 -0400
Message-id: <AANLkTin_Dz7E_8ZUf13YKcm2-1+0kkECryz4oOh3sm8X@xxxxxxxxxxxxxx>
Ali --

Good point about the interchange pitfalls caused by different meanings assigned to Company A and Company B's logics by their different model theories/engines. 

A common intermediate pivot notation does not solve the problem -- A and B would have to agree to replace their engines by the engine for the pivot logic in order to get the same results . RIF users, beware!

For the special case of interchanging rules between organizations, there are some other suggested methods in [1].  The methods appear also to apply to the more general case you describe.

                      Cheers,  -- Adrian

[1]  www.w3.org/2004/12/rules-ws/paper/19

Internet Business Logic
A Wiki and SOA Endpoint for Executable Open Vocabulary English Q/A over SQL and RDF
Online at www.reengineeringllc.com   
Shared use is free, and there are no advertisements

Adrian Walker

On Thu, Aug 12, 2010 at 11:08 AM, Ali Hashemi <ali@xxxxxxxxx> wrote:
To add one more perspective to this discussion.

From a very practical standpoint, the proliferation of "guaranteed logics" has at least two unintended consequences.

1) Company A uses decidable logic L1 (say an internally developed temporal logic), while Company B uses decidable logic L2 (say OWL-DL). Later A and B realize they want to exchange information and/or combine systems. The model and proof theory of their logics are somewhat idiosyncratic. Without a more encompassing framework (i.e. Common Logic?) or a common semantic foundation, the translation between these logics (syntax, semantics and all), let alone their axioms is at best not trivial.

Perhaps this situation is mitigated if someone somewhere specifies mappings from L1 and L2 to some common foundation logic (see http://www.informatik.uni-bremen.de/agbkb/forschung/formal_methods/CoFI/hets/index_e.htm ). But note, that for each dialect of a logic (not just the ontology), a further mapping is needed. Unless of course we can somehow make sure that everyone uses the same specialized logic...

2) As a corollary to what John describes below, by sacrificing expressiveness for decidability, we also further hinder interoperability. Particularly, if we only represent the fragment of the problem under consideration that is expressible in said language, we are leaving a lot of the intended semantics of the problem domain external to the system of representation!

Any other person or machine coming along can at best only guess at what the actual intent of these squiggles are, since so much is consequently left unsaid. A lot of the problems that arise when trying to conduct semantic / ontology mappings become much more directly accessible. One need only look at the current state of the art in semantic mapping based on DL's to see the problems posed by this approach. We're trying to match lexical terms, guessing at instance data and using probabilities to guess at the intended semantics. If more were expressed, we could actually use model theory to specify much more robust and reliable mappings.

Note: one can still decide to infer / implement only particular fragments of the representation, but the representation is more complete and closer to the intended semantics of the ontologist / knowledge engineer.


None of this is meant to take anything away from the work done on OWL or DL's, but I submit that the framing or promoting of these languages as "more appropriate" ontology languages, because they guarantee decidability is missing the mark, and probably counter productive and needlessly divisive / creating silos in a community that really can't afford to fragment.

Fragments of logic which exhibit certain desirable properties are an important / invaluable toolkit in any ontologist / knowledge engineer's repertoire. Being able to mark a fragment of an ontology as exhibiting XYZ properties and guaranteeing ABC performance is important, and can make the difference in certain domains. But it is not the same as ontology, and it would be disingenuous to construe such languages as being somehow inherently more suited to computational ontology.

To my limited mind, they represent one of many useful applications. If I'm designing an autonomous robot, I'll probably be using a dedicated temporal reasoner, a dedicated spatial reasoner, etc. etc. OWL-2 is probably too expressive for these, and not nearly expressive enough to support narrative. No single optimized logic or formalism on its own is likely to suffice, and I'd rather represent as much as I can formally, and then worry about how best to compute these explicit assumptions - probably (no - in fact, exactly) based on the invaluable work that people in the DL community are doing determining the properties of various fragments of FOL. But to start with DL's as the end all seems sort of like lobotomizing logic...

My two cents.


On Thu, Aug 12, 2010 at 2:37 AM, John F. Sowa <sowa@xxxxxxxxxxx> wrote:
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.

Yes, and some groups, including Cyc and VivoMind, go a bit farther:

 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.

 2. If you use a very expressive logic, you are not required to use
    all possible features of that logic in every problem.

 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.)

 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).

 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.

> 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

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.

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.

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).

> 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.

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.

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:

   Fads and fallacies about logic


(•`'·.¸(`'·.¸(•)¸.·'´)¸.·'´•) .,.,

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

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    (01)

<Prev in Thread] Current Thread [Next in Thread>
  • [ontolog-forum] Logic Interchange Gotchas (Was: owl2 and cycL/cycML), Adrian Walker <=