**Authors: Eiji Takimoto, Akira Miyashiro, Akira Maruoka, and Yoshifumi Sakai**.

Email: t2@eceit.tohoku.ac.jp

**Source: ***Theoretical Computer Science* Vol. 185,
No. 1, 1997, 177-190.

**Abstract.**
In the PAC-learning, or the query learning model, it has been an
important open problem to decide whether the class of DNF and CNF
formulas is learnable. Recently, it was pointed out that the problem of
PAC-learning for these classes with membership queries can be reduced
to that of learning for the class of *k*-quasi Horn formulas with
membership and equivalence queries. A *k*-quasi Horn formula is a CNF
formula with each clause containing at most *k* unnegated literals. In this
paper, notions of *F*-Horn formulas and *l-F*-Horn formulas, which are
extensions of *k*-quasi formulas, are introduced, and it is shown that the
problem of query learning for DNF and CNF formulas with membership
and equivalence queries can be reduced to that for *l-F*-Horn formulas for
an appropriate choice of *F*. It is shown that under a condition on *F*, the
class of orthogonal *F*-Horn formulas is learnable with membership,
equivalence and subset queries. Moreover, it is shown that under the same
condition the class of orthogonal *l-F*-Horn formulas is learnable with
membership and equivalence queries. For the latter result, the condition
of orthogonality of *F*-Horn formulas is crucial because, if the statement
held without the condition, then the result would imply that DNF and
CNF are exactly learnable with membership and equivalence queries.

©Copyright 1997 Elsevier Science