Andrew Wohlgemuth, George Markowsky
Mathematical Biosciences
Given a set, S, of Boolean n-vectors, one can choose k of the n coordinate positions and consider the set of k-vectors which results by keeping only the designated k positions of each vector, i.e., from k-projecting S. In this paper, we study the question of finding sets S as small as possible such that every k-projection of S yields all the 2k possible k-vectors. We solve this problem constructively and almost optimally for k=2 and all n. For k≧3, the constructive solutions we describe are much larger than an O(k 2k log n) nonconstructive upper bound which we derive. The nonconstructive approach allows us to generate fairly small sets S which have a very high probability of having the surjective k-projection property. © 1983 Springer-Verlag.
Andrew Wohlgemuth, George Markowsky
Mathematical Biosciences
George Markowsky, Andrew Wohlgemuth
Mathematical Biosciences
Alok Aggarwal, Ashok K. Chandra, et al.
SPAA 1989
Ashok K. Chandra, Steven Fortune, et al.
Journal of Computer and System Sciences