Parallel Transitive Reasoning in Mixed Relational Hierarchies

Class hierarchies have been used tradition ally in Knowledge Representation and Reasoning for a number of purposes such as in heritance, classification and transitive closure reasoning. In the last several years we have been following two lines of investigation to extend this kind of research. From a conceptual level we have worked on techniques to extend such reasoning to hierarchies other than the IS-A hierarchy. Specifically, we have developed a model of inheritance for part hi erarchies (Halper 1992, Halper 1993, Halper 1994). From an implementation point of view we have worked on building fast reasoners based on massively parallel representations of IS-A, Part-of, Contained-in, etc. hierarchies (Lee 1993, Lee 1995, Lee 1996a, Geller 1991a, Geller 1991b, Geller 1993a, Geller 1993b, Geller 1994a, Geller 1994b). How ever, in all this work we assumed that there exist separate hierarchies. In an often-cited paper by Winston, Chaffin, and Hermann (Winston 1987) a model of reasoning is intro duced that permits the combination of IS-A, Part-of, and Contained-in in a single hierarchy. The purpose of our paper is to present representational constructs and reasoning algorithms that combine these three ingredients: mixed relation hierarchies, transitive closure reasoning, and massively parallel algorithms. It is hoped that this combination will lead to progress both in better approximating human commonsense reasoning and in better approximating human speed of rea soning. We conclude the paper with a brief description of a medical vocabulary that we have been using as a source of test data.