Larry Watanabe and Larry Rendell
The problem of computing maximally-specific generalizations (MSCG~) of relational descriptions can be modelled as tree search. We describe several transformations and pruning methods for reducing the complexity of the problem. Based on this analysis, we have implemented a search program (X-search) for finding the MSCG’s. Experiments compare the separate and combined effects of pruning methods on search efficiency. With effective pruning methods, full-width search appears feasible for moderately sized relational descriptions.