"Interactive Learning of Monotone Boolean Functions"

Information Sciences, 1996, Vol. 94, Nos. 1-4, pp. 87-118.

B. Kovalerchuk, E. Triantaphyllou, A.S. Deshpande and E. Vityaev

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 [11]. 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 f1 and f2. This formulation allows to further decrease the dialogue with an expert and restore non- monotone functions of the form f2&~f1. The effectiveness of the proposed approaches is demonstrated by some illustrative computational experiments.

Key Words:
No key words were required by this journal.

Download this paper as a PS (PostScript) file (size = 1,836 KB).

Download this paper as a PDF file (size = 2,976 KB).

Return to Dr. Triantaphyllou's Homepage.