Or (just to keep the record clear) another option is to simply abandon
this quest to achieve decideability, and work with semi-decideable
complete logics such as classical FOL. This is of course utterly
foreign to the entire description-logic tradition within which Ian
works, but it is a viable stance to adopt. (01)
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 when they are wanting to discover what is entailed by
what, or whether some body of sentences are satisfiable, or subsumed
by another. However, one might take the view that such guarantees are
inherently unlikely to be worth a great deal, given that large
problems are routinely too difficult for actual reasoning engines even
within a decideable logic, and users will have to make do with
pragmatic judgements based on imperfect tests which sometimes fail to
yield results. Think of this as analogous to a 404 error resulting
from a failed hyperlink GET operation, and it seems to me to be in
perfect harmony with the zeitgeist of the Web: a global compromise in
which one accepts the possibility of failure in order to achieve the
simplicity and efficiency gotten by the use of non-guaranteed methods.
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. (02)
But let me not start up this (old) argument in this forum. I only
wanted to put this point of view into the record as one viable option.
It bears the same kind of relationship to discussions about the merits
of OWL vs. RIF, and the problem of how to achieve decideability, that
atheism does to comparative theology. I do not expect it be any more
popular. (03)
Pat (04)
On Aug 2, 2010, at 2:05 PM, Ian Horrocks wrote: (05)
> Adrian,
>
> I think you misunderstood the problem. The problem is that extending
> OWL (or similar logics) with the ability to express such cycles
> would, in the general case, immediately lead to undecidability. Of
> course one can restore decidability in other ways, most notably by
> ensuring that there is always a known upper bound on the the size of
> models. Decidability is then an easy consequence of the fact that we
> can build and check all relevant models. This is the approach taken
> in LP. In logics like OWL, decidability is a consequence of (some
> form of) the tree model property. Both approaches restrict what it
> is possible to express. The problem is finding a way to combine the
> (good) features of both approaches without loosing decidability.
> This problem has yet to be solved, and in some senses it is
> inherently unsolvable.
>
> Regards,
> Ian
>
> p.s. As I think someone else pointed out, OWL 2 can express
> something similar to "transitive over", which, like transitivity,
> does lead to some weakening of the tree model property, but with
> some restrictions on the structure of "transitive over" axioms it is
> possible to ensure that the language is still decidable.
>
>
>
> On 31 Jul 2010, at 14:47, Adrian Walker wrote:
>
>> Hi John & All,
>>
>> The difficulties with OWL, cycles and decidability that you mention
>> were solved in the logic programming literature in the 1980s and
>> 90s [1,2 and many subsequent papers], as follows. Allow recursion,
>> and use the unique minimal model semantics that comes with Horn
>> clauses. The cyclic examples you mention are then easy, and the
>> approach covers other situations, such as "transitive over" [3]
>> that appear to be beyond OWL.
>>
>> Some of the logic programming (LP) literature seems to be informing
>> the W3C Rule Interchange (RIF) work at the W3C.
>>
>> There would seem to be an opportunity here for a paper arguing that
>> both the OWL and RIF-LP approaches are necessary.
>>
>> Cheers, -- Adrian
>>
>>
>> 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
>> Reengineering
>>
>> [1] Towards a Theory of Declarative Knowledge, (K. Apt, H. Blair,
>> A. Walker). In: Foundations of Deductive Databases and Logic
>> Programming, J. Minker (Ed.), Morgan Kaufman 1988.
>>
>> [2] Backchain Iteration: Towards a Practical Inference Method that
>> is Simple Enough to be Proved Terminating, Sound and Complete.
>> Journal of Automated Reasoning, 11:1-22.
>>
>> [3] www.reengineeringllc.com/demo_agents/TransitiveOver1.agent
>>
>>
>> On Sat, Jul 31, 2010 at 5:17 AM, <sowa@xxxxxxxxxxx> wrote:
>>
>>
>>
>> Cameron, Ian, et al.,
>>
>>> Wouldn't Common Logic be the
>> "logical" choice if one were to
>>> relinquish
>> decidability? It's an ISO standard and tools are gradually
>>>
>> starting to appear.
>>
>>>> OWL and CycL are not really
>> comparable, because OWL is based on a
>>>> fragment of First
>> Order Logic that is known to be decidable, for which
>>>>
>> provably correct reasoning algorithms are known and for which
>> effective
>>
>>>> implementations based on said algorithms are available.
>> OWL's expressive
>>>> power could, of course, be easily (indeed
>> arbitrarily) extended if one
>>>> were prepared to compromise on
>> some or all of these design constraints...
>> I am on my way home from
>> Malaysia, where three collocated conferences discussed these and
>> other
>> issues: MJCAI (Malaysia Joint Conference on AI), ICCS (International
>> Conference on Conceptual Structures), and STAKE (Semantic
>> Technology And
>> Knowledge Engineering).
>> One of the invited speakers, Boris Motik,
>> wrote his PhD dissertation on DLs, and he is now teaching at
>> Oxford. He
>> made the observation that the desire to enforce decidable models
>> led to
>> many dubious compromises, such as the limitation to tree-structured
>> models. Unfortunately, such models cannot represent any structures
>> that
>> contain cycles.
>> One example would be a benzene ring. You can
>> represent a structure with 6 carbon atoms, but you can't say that the
>> sixth atom is connected to the first because that would create a
>> cycle.
>> Instead of describing just one fixed intended model, a typical OWL
>> description would have a huge number of models. (There are ways of
>> getting around such restrictions, but they involve jumping through
>> lots of
>> hoops with a large number of complex conditions to state something
>> very
>> simple.)
>> As another example, Botik showed a simple OWL description
>> of the human heart. Unfortunately, that description had an
>> infinity of
>> models. One model had exactly one left ventricle (which most people
>> have). But other models could have any number of left ventricles.
>> There
>> was no way to limit the intended models to those that have just one
>> left
>> ventricle.
>> As a solution, Botik proposed an extension to OWL that
>> allowed arbitrary finite graphs, which could contain cycles. As a
>> convenient notation for that extension, he drew diagrams that
>> looked very
>> much like simple (non-nested) conceptual graphs.
>> OWL should
>> be considered an open-ended family of languages, starting with OWL
>> full,
>> OWL lite, OWL DL, OWL 2.0, SWRL, OWL-Graph, etc., etc., etc.
>> These
>> versions of OWL have only two things in common: the three letters
>> O-W-L
>> in their name, and the fact that every one of them is a dialect of
>> Common
>> Logic.
>> Since this thread is also addressing CycL, we should point
>> out that CycL could also be considered a dialect of Common Logic.
>> CycL
>> and CL are very easily comparable to OWL: They are supersets of
>> all the
>> OWL versions and they can be used to relate each and every one of
>> them.
>> That is a very useful property.
>> As for undecidability, it is an
>> interesting theoretical property. But Lenat and other Cyclers have
>> observed that in the 26 years of Cyc, undecidability has never
>> caused any
>> serious problems for any practical application.
>> Occasionally, a
>> collection of Cyc axioms might cause one of their inference engines
>> to get
>> hung up in a loop. That is also true of every major programming
>> language. Java, C, Fortran, etc. are all undecidable, and nobody
>> cares. Programmers use methods of structured programming and design
>> patterns that enable them to predict when they have safe programs,
>> and
>> they have a very large number of guidelines for ways of avoiding the
>> infinite loops.
>> If anyone asks how many tools are available for
>> Common Logic, the short answer is the sum total of all the tools
>> written
>> for any and every dialect of Common Logic. That includes all the
>> Semantic
>> Web languages, all the theorem provers used for tptp.org, and huge
>> numbers
>> of experimental and commercial tools available today. Among other
>> things,
>> Common Logic has been used to define the semantics of the UML
>> diagrams
>> (check Google for fUML or formal UML). So all of the UML diagrams
>> can be
>> considered dialects of Common Logic, and all the UML tools can be
>> considered CL tools.
>> The advantage of CL is the ability to relate
>> anything stated in any of those languages to any other language.
>> Very few
>> logics have that property.
>> When I get back home, I'll send more info
>> with references to the details.
>> John
>>
>>
>>
>> _________________________________________________________________
>> 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
>
>
> _________________________________________________________________
> 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
>
> (06)
------------------------------------------------------------
IHMC (850)434 8903 or (650)494 3973
40 South Alcaniz St. (850)202 4416 office
Pensacola (850)202 4440 fax
FL 32502 (850)291 0667 mobile
phayesAT-SIGNihmc.us http://www.ihmc.us/users/phayes (07)
_________________________________________________________________
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 (08)
|