PARTS INFERENCE: Closed and Semi-Closed Partitioning Graphs

Abstract

Ma consider the problem of answering part-of questions and questions about overlap in partitioning structures. which is of importance in A. I. systems knowledgeable about parts relationships, set inclusion relationships or taxonomies of types in an earlier paper It was noted that the problem of extracting information from arbitrary sets of partitioning assertions (P-graphs) is intractable (at least if P = NP) and the more restrictive class of quasi-hierarchical closed P-graphs was introduced as a fairly flexible representation of partitioning structures permitting efficient information extraction. The present paper introduces the larger class of semi-closed P-graphs. and provides efficient and complete methods for answering part-of and disjointness questions based on such P-graphs.