Analysis of Case-Based Representability of Boolean Functions by Monotone Theory Author: Ken Satoh Source: Lecture Notes in Artificial Intelligence Vol. 1501, 1998, 179 - 190. Abstract. Classification is one of major tasks in case-based reasoning(CBR) and many studies have been done for analyzing properties of case-based classification [1, 14, 10, 15, 12, 9, 13, 7]. However, these studies only consider numerical similarity measures whereas there are other kinds of similarity measure for different tasks. Among these measures, HYPO system [2, 3] in a legal domain uses a similarity measure based on set inclusion of differences of attributes in cases. In this paper, we give an analysis of representability of boolean functions in case-based classification using the above set inclusion based similarity. We show that such case-based classification has a strong connection between monotone theory studied in [4, 11]. Monotone theory is originated from computational learning theory and is used to show learnability of boolean function with polynomial DNF size and polynomial CNF size [4] and is used for deductive reasoning as well [11]. In this paper, we analyze a case-based representability of boolean functions by using the above relationship between the case-based classification by set inclusion based similarity and the monotone theory. We show that any boolean function is representable by a casebase whose size is bounded in polynomial of its DNF size and its CNF size and thus, k-term DNF, k-clause CNF can be efficiently representable in a casebase using set inclusion similarity. ©Copyright 1998 Springer