**Mail folder:**Interlingua Mail**Next message:**Richard Fikes: "AAAI Meeting Attendees"**Previous message:**Michael Genesereth: "news"

Organization: Universitaet des Saarlandes D-6600 Saarbruecken FRG Message-id: <9007271008.AA09378@fb14vax.cs.uni-sb.de> To: interlingua@vaxa.isi.edu Cc: nebel@cs.uni-sb.de Subject: Recursive Defs Date: Fri, 27 Jul 90 12:08:04 N From: nebel@cs.uni-sb.de

>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 --------