Interactive learning of monotone Boolean functions

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 fo...

Full description

Saved in:
Bibliographic Details
Published in:Information sciences 1996-10, Vol.94 (1), p.87-118
Main Authors: Kovalerchuk, Boris, Triantaphyllou, Evangelos, Deshpande, Aniruddha S., Vityaev, Evgenii
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 f 1 and f 2. This formulation allows one to further decrease the dialogue with an expert and restore nonmonotone functions of the form f 2&|f 1 . The effectiveness of the proposed approaches is demonstrated by some illustrative computational experiments.
ISSN:0020-0255
1872-6291
DOI:10.1016/0020-0255(96)00082-5