Logical analysis of binary data with missing bits

We model a given pair of sets of positive and negative examples, each of wh ich 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 eq ual 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 (respec tively, false) for every vector in (T) over tilde (respectively, in (F) ove r tilde). This is a fundamental problem, encountered in many areas such as learning theory, pattern recognition, example-based knowledge bases, logica l analysis of data, knowledge discovery and data mining. In this paper, dep ending upon how to deal with missing bits, we formulate three types of exte nsions called robust, consistent and most robust extensions, for various cl asses of Boolean functions such as general, positive, Hem, threshold, decom posable and k-DNF. The complexity of the associated problems are then clari fied; some of them are solvable in polynomial time while the others are NP- hard. (C) 1999 Elsevier Science B.V. All rights reserved.