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