Set containment inference and syllogisms (Q1114429)

Type hierarchies and type inclusion is standard in many knowledge representation schemes. In this paper, it is shown how to determine consistency and inference for collections of statements of the form: ``mammal isa vertebrate''. These containment statements relate to contents of two sets or types. The work here is new in permitting statements with negative information: disjointness of sets, or non- inclusion of sets. It is shown that binary containment inference is solved by rules essentially equivalent to Aristoteles' syllogisms. Necessary and sufficient conditions for consistency as well as sound and complete sets of inference rules, are presented for binary containment. The sets of inference rules are compact, and lead to polynomial-time inference algorithms, so permitting negative constraints does not result in intractability for this problem.