This article is cited in 2 papers

Part 3. Mathematical models

Learning of Boolean fixed-weight functions

A. V. Bistrigova

Lomonosov Moscow State University

Abstract: This paper is concerned with the learning complexity of Boolean fixed-weight functions using membership queries, comparation queries, equivalence queries, and extended equivalence queries. Moreover, it is allowed to use only one type of queries during learning. This paper gives exact values of learning complexity for all the types of queries besides comparation queries. The paper presents the upper bound on learning complexity for comparation queries. In addition, the paper demonstrates that the upper bound is equal to the lower bound for the 1-, 2-, 3-weight functions.

Keywords: Boolean fixed-weight functions, membership queries, comparation queries, equivalence queries, extended equivalence queries, exact learning.