A Boolean function is called k-convex if for any pair x,y of its true point
s at Hamming distance at most k, every point "between" x and y is also true
. Given a set of true points and a set of false points, the central questio
n of Logical Analysis of Data is the study of those Boolean functions whose
values agree with those of the given points. In this paper we examine data
sets which admit k-convex Boolean extensions. We provide polynomial algori
thms for finding a k-convex extension, if any, and for finding the maximum
k for which a k-convex extension exists. We study the problem of uniqueness
, and provide a polynomial algorithm for checking whether all k-convex exte
nsions agree in a point outside the given data set. We estimate the number
of k-convex Boolean functions, and show that for small k this number is dou
bly exponential. On the other hand, we also show that for large k the class
of k-convex Boolean functions is PAC-learnable. (C) 2000 Elsevier Science
B.V. All rights reserved.