TY - JOUR

T1 - Learning monotone log-term DNF formulas under the uniform distribution

AU - Sakai, Y.

AU - Maruoka, A.

PY - 2000

Y1 - 2000

N2 - Based on the uniform distribution PAC learning model, the learnability for the class of monotone disjunctive normal form formulas with at most O (log n) terms, denoted O (log n)-term MDNF, is investigated. Using the technique of restriction, an algorithm that learns O (log n)-term MDNF by examples in polynomial time is given.

AB - Based on the uniform distribution PAC learning model, the learnability for the class of monotone disjunctive normal form formulas with at most O (log n) terms, denoted O (log n)-term MDNF, is investigated. Using the technique of restriction, an algorithm that learns O (log n)-term MDNF by examples in polynomial time is given.

UR - http://www.scopus.com/inward/record.url?scp=0034406593&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0034406593&partnerID=8YFLogxK

U2 - 10.1007/s002249910002

DO - 10.1007/s002249910002

M3 - Article

AN - SCOPUS:0034406593

SN - 1432-4350

VL - 33

SP - 17

EP - 33

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 1

ER -