Learning a subclass of k-quasi-Horn formulas with membership queries

Boolean formulas have been widely studied in the field of learning theory. We focus on the model of learning with queries, and study a restriction of the class of k-quasi-Horn formulas, that is, conjunctive normal form formulas where the number of unnegated literals per clause is at most k. This class is known to be as hard to learn as the general class CNF of conjunctive normal form formulas. By imposing some constraints, we define a fragment of this logic that can be learned using only membership queries. Also we prove that none of these constraints makes by itself the class learnable.

► We study a subclass of k-quasi-Horn formulas. ► We show a learning algorithm with membership queries alone for the restricted class. ► We prove that without the restrictions we impose the class cannot be learned. ► We prove that the restricted class cannot be learned with only equivalence queries.