Adrian, (01)
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. (02)
Regards,
Ian (03)
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. (04)
On 31 Jul 2010, at 14:47, Adrian Walker wrote: (05)
> 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 (06)
_________________________________________________________________
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 (07)
|