TY - JOUR

T1 - The learnability of exclusive-or expansions based on monotone DNF formulas

AU - Takimoto, Eiji

AU - Sakai, Yoshifumi

AU - Maruoka, Akira

PY - 2000/6/28

Y1 - 2000/6/28

N2 - The learnability of the class of exclusive-or expansions based on monotone DNF formulas is investigated. The class consists of the formulas of the form f = f1 ⊕⋯⊕ fd, where f1 > ⋯ > fd are monotone DNF formulas. It is shown that any Boolean function can be represented as a formula in this class, and that the representation in the simplest form is unique. Learning algorithms that learn such formulas using various queries are presented: An algorithm with subset and superset queries and one with membership and equivalence queries are given. The former can learn any formula in the class, while the latter is proved to learn formulas of constant depth, i.e., formulas represented as exclusive-or of a constant number of monotone DNF formulas. In spite of the seemingly strong restriction of the depth being constant, the class of formulas of constant depth includes functions with very high complexity in terms of DNF and CNF representations, so the latter algorithm could learn Boolean functions significantly complex otherwise represented.

AB - The learnability of the class of exclusive-or expansions based on monotone DNF formulas is investigated. The class consists of the formulas of the form f = f1 ⊕⋯⊕ fd, where f1 > ⋯ > fd are monotone DNF formulas. It is shown that any Boolean function can be represented as a formula in this class, and that the representation in the simplest form is unique. Learning algorithms that learn such formulas using various queries are presented: An algorithm with subset and superset queries and one with membership and equivalence queries are given. The former can learn any formula in the class, while the latter is proved to learn formulas of constant depth, i.e., formulas represented as exclusive-or of a constant number of monotone DNF formulas. In spite of the seemingly strong restriction of the depth being constant, the class of formulas of constant depth includes functions with very high complexity in terms of DNF and CNF representations, so the latter algorithm could learn Boolean functions significantly complex otherwise represented.

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

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

U2 - 10.1016/S0304-3975(99)00265-0

DO - 10.1016/S0304-3975(99)00265-0

M3 - Article

AN - SCOPUS:0346076857

SN - 0304-3975

VL - 241

SP - 37

EP - 50

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-2

ER -