Recursive Defs
Organization: Universitaet des Saarlandes
              D-6600 Saarbruecken FRG
Message-id: <>
Subject: Recursive Defs
Date: Fri, 27 Jul 90 12:08:04 N
>I am curious about Nebel's approach to recursive definitions.
>All approaches I am familiar with involve axiom schemes for
>mathematical induction (recursion and induction appear to be
>closely related).  Is this also true of Nebel's approach?
>Could Nebel's mechanism conclude that every descendent of a
>human is human?

Let me briefly summarize my (and Franz Baader's) results:

1) If the semantics of a "terminological logic" is straightforwardly
extended to cover cyclic/recursive definitions you will be able to
conclude that "every descendent of a human is a human" (and/or that
every parent of a human is a human), but you do not get subsumption
relationships between concepts that are structurally similar, such as
"A = (all R A)" and "B = (all R B)". This is similar to FOL where
recursively defined predicates which are defined using the same
structure may be interpreted differently, e.g.  "A(x) <=> (A(f(x)) or
x=0)" and "B(x) <=> (B(f(x)) or x=0)". The reason is that there are many
possible models for A and B. Whether such a behavior is an advantage
or not is arguable. If you want "truly" recursive definitions you have
to consider "standard" models, such as the least one (which
corresponds to the induction principle) or the greatest one.

2) It is possible to define the notion of greatest and least models
for terminological logics -- provided you do not have negation in
your language -- and to characterize them as fixpoints of a monotonic
model-generating operator (Thus, here we come to models where the
induction principle is valid). Funny enough, the least models (or
fixpoints) appear to be counter-intutive in this context -- at least
in a setting where you have ALL and AND concept-forming operators.
Greatest models on the other hand are well-behaved. In particular, it
is possible to characterize subsumption relationships w.r.t. to such a
semantics by inclusion between regular languages (for terminological
languages containing only AND and ALL) [Franz Baader gives a talk
about this issue at AAAI].

3) If you introduce negation in the terminological language the
model-generating operator is not monotonic any longer (this is
parallel to the case we have in logic programming), i.e., we don't
know whether least or greatest models exist. One could use 
iterating fixpoint constructions and other model preference relations
then. However, I never investigated such possibilities. 

4) Computational issues: Allowing cycles increases the complexity of
subsumption determination. In the case of a terminological language
containing only ALL and AND from NP-complete to PSPACE-complete. If
you add coreference constraints over chains of functional roles
(as used in the CLASSIC language) subsumption w/o cycles is decidable,
with cycles it becomes undecidable. These results are (almost)
completely independent of the semantics one chooses.

There are two papers concerning the issues above: One by Franz Baader
and one by me. If you are interested to receive copies of these
papers, just drop me a note with your mail-address.

-- Bernhard