This paper presents some optimal interactive algorithms for some problems related to learning of monotone Boolean functions. These algorithms are based on the fundamental Hansel theorem. The advantage of the algorithms is that they are not heuristics, as is often the case of many known algorithms for general Boolean functions, but they are optimal in the sense of the Shannon function. This paper also formulates a new problem for the joint restoration of two nested monotone Boolean functions fl and f2. This formulation allows one to further decrease the dialogue with an expert and restore nonmonotone functions of the form f2&lfl. The effectiveness of the proposed approaches is demonstrated by some illustrative computational experiments.
['Boris Kovalerchuck', 'Evangelos Triantaphyllou', 'Aniruddha S. Deshpande', 'Evgenii Vityaev']
Interactive learning of monotone Boolean functions