"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
Abstract:
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.
