Logical analysis of binary data with missing bits

We model a given pair of sets of positive and negative examples, each of which may contain missing components, as a partially defined Boolean function with missing bits (pBmb) ((T) over tilde, (F) over tilde), where (T) over tilde subset of or equal to {0, 1, *}(n) and (F) over tilde subset of or equal to {0, 1, *}(n), and "*" stands for a missing bit. Then we consider the problem of establishing a Boolean function (an extension) f : {0, 1}(n) --> {0, 1} belonging to a given function class C, such that f is true (respectively, false) for every vector in (T) over tilde (respectively, in (F) over tilde). This is a fundamental problem, encountered in many areas such as learning theory, pattern recognition, example-based knowledge bases, logical analysis of data, knowledge discovery and data mining. In this paper, depending upon how to deal with missing bits, we formulate three types of extensions called robust, consistent and most robust extensions, for various classes of Boolean functions such as general, positive, Hem, threshold, decomposable and k-DNF. The complexity of the associated problems are then clarified; some of them are solvable in polynomial time while the others are NP-hard. (C) 1999 Elsevier Science B.V. All rights reserved.