A FAST AND SIMPLE ALGORITHM FOR IDENTIFYING 2-MONOTONIC POSITIVE BOOLEAN FUNCTIONS

Consider the problem of identifying min T(f) and max F(f) of a positiv e (i.e., monotone) Boolean function f, by using membership queries onl y, where min T(f) (max F(f)) denotes the set of minimal true vectors ( maximum false vectors) of f. Moreover, as the existence of a polynomia l total time algorithm (i.e., polynomial time in the length of input a nd output) for this problem is still open, we consider here a restrict ed problem: given an unknown positive function f of n variables, decid e whether f is 2-monotonic or not, and if f is 2-monotonic, output bot h min T(f) and max F(f). For this problem, we propose a simple algorit hm, which is based on the concept of maximum latency, and we show that it uses O(n(2)m) time and O(n(2)m) queries, where m = \min r(f)\ + \m ax F(f)\. This answers affirmatively the conjecture raised in Bores et al. [Lecture Notes in Comput. Sci. 557 (1991), 101-115], Bores et al. [SIAM J. Comput. 26 (1997), 93-109], and is an improvement over the t wo algorithms discussed therein: one uses O(n(3)m) time and O(n(3)m) q ueries, and the other uses O(nm(2) + n(2)m) time and O(nm) queries. (C ) 1998 Academic Press.