Learning Read-Once Functions Individually

The paper considers special properties of graphs linked to read-once functions and the task of learning them individually. A main theorem characterizing the set of all checking tests is proved; the results are applied to the problem of learning with respect to read-once alternatives in the basis of all two-variable functions. Individual upper bounds for minimal test length are obtained and a sequence of easily learned functions is constructed.