Re: Recursive Defs
nebel@cs.uni-sb.de
Organization: Universitaet des Saarlandes
D-6600 Saarbruecken FRG
Message-id: <9007301335.AA22549@fb14vax.cs.uni-sb.de>
To: "David A. McAllester" <dam@AI.MIT.EDU>
Cc: nebel@cs.uni-sb.de, interlingua@vaxa.isi.edu
Subject: Re: Recursive Defs
In-Reply-To: Your message of Fri, 27 Jul 90 11:40:00 -0400.
<19900727154048.2.DAM@CROCE.AI.MIT.EDU>
Date: Mon, 30 Jul 90 15:35:37 N
From: nebel@cs.uni-sb.de
David:
I agree with your 2nd remark that "the whole idea of a definition ...
is that the meaning of a new symbol is completely specified be the
meaning of ... "more basic symbols" (but see below). On a semantic
level this means that the denotation of your symbol is completely
determined by the "more basic symbols" and the way these are composed,
i.e., given the denotation of your basic symbols you want to end up
with a unique denotation of the new symbol, and this is the entire
idea behind the fixpoint business.
>1) I don't believe that your semantics allows you to conclude
>that every descendent of a human is human.
Let me first present the solution I had in mind when we were talking
about descendents:
human < (and mammal (all child-of human))
This gives you for all styles of semantics and all natural numbers n:
human(x) and child-of^{n}(x,y) => human(y)
I have not defined the relation "descendent-of", though, but thought
of it as the iterated child-of relation.
> Consider
>
>(descendent-of x y) <=> (or (child-of x y) (exists (z) (child-of x z) (descendent-of z y)))
>
>This is the definition of descendent that I had in mind (the intent
>is to define descendent-of as the transitive closure of child-of).
>
>Now suppose we have
>
>(and (human x) (child-of x y)) => (human y)
>
>There exist fixed points of the descendent-of definition (like the
>maximal fixed point) where there are descendents of humans that are not human.
You are correct, maximal fixpoints may contain non-human descendents in this
case. The situation is even worse, however. There may not be any
greatest or least fixpoint because the operator on interpretations is
not monotonic. Making the denotation of descendent-of larger could lead
to the shrinkage of the denotation of the expression
(lambda (x) (and (human x) (forall y: (descendent-of x y) => (human y))))
or equivalently in terminological logic
(and human (all descendent-of human))
You could use an iteration of fixpoints: First roles (2-place
predicates), then concepts (1-place predicates), which works as long
as you do not try to define a role in terms of concepts, which use the
role to be defined.
Summarizing, (greatest or least) fix-point models do not always exist,
in particular if you use unrestricted FOL (This is, however, something
we know already from logic programming).
A side remark: Franz Baader suggests to add a transitive closure
operator over roles to terminological logics (because he claims that
this is what cyclic definitions are good for) and to prohibit
terminological cycles. This may also be the solution for the example above.
>3) Your examples of counter-intuitive consequences of least fixed point
>semantics are not convincing. The examples involve ``defining'' terms
>that are clearly natural kinds, such as human.
The main problem with the least fixpoint is that the denotations of
concepts can become empty. Granting that "human" is a natural kind, I
would at least like to be able to state
necessary conditions such as that every child is a
human and that a human has 2 parents:
human < (and mammal (all child human) (all parent human) (atleast 2 parents))
Because of the (atleast 2 parents) expression, we end up with an empty
denotation.
Let me finally correct of a what I conceived as a misconception: In my
two papers about cycles I do not propose to consider one of the
semantic styles as the only and right one. Rather I investigate the
different styles and analyze their consequences claiming that the
"descriptive" style may be the adequate one (Thus, "my semantics" or
"my approach" is something I have no unique denotation for). The
justification for preferring "descriptive sematics" is that my
motivation to investigate cycles in terminological logics was to
explain the formal semantics of terminological KB's designed for NL
purposes (as, e.g., the JANUS KB). These heavily rely on cycles and
use them in a non-definitional way. The reason behind that is
probably that in NL applications most concepts are non-definitional in
any case. Rather what you have is a web of concepts connected by
different relations, which may even be cyclic (a brief look into a
dictionary should convince you that this is indeed the case). For
such an application, descriptive semantics is the right thing to use,
I believe, although, admittedly, you no longer have a definitional
formalism and the "term introductions" are assertional biconditionals
(as you remarked in your third point).
--------