TY - GEN

T1 - Learning monotone log-term DNF formulas

AU - Sakai, Yoshifumi

AU - Maruoka, Akira

N1 - Publisher Copyright:
© 1994 ACM.

PY - 1994/7/16

Y1 - 1994/7/16

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

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

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

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

U2 - 10.1145/180139.181095

DO - 10.1145/180139.181095

M3 - Conference contribution

AN - SCOPUS:0039248100

T3 - Proceedings of the Annual ACM Conference on Computational Learning Theory

SP - 165

EP - 172

BT - Proceedings of the 7th Annual Conference on Computational Learning Theory, COLT 1994

PB - Association for Computing Machinery

T2 - 7th Annual Conference on Computational Learning Theory, COLT 1994

Y2 - 12 July 1994 through 15 July 1994

ER -