On Learning Read-k-Satisfy-j DNF

DOI10.1137/S0097539794274398MaRDI QIDQ4210120zbMATH OpenOpenAlexFDO

Authors Howard Aizenstein, Roni Khardon, Eyal Kushilevitz, Leonard Pitt, Avrim Blum

Publication date 21 September 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539794274398

zbMATH Keywords

computational learning theorydecision treesDNFlearning

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05)

Recommendations

• Read-twice DNF formulas are properly learnable
• Proper learning of \(k\)-term DNF formulas from satisfying assignments
• Fast learning of \(k\)-term DNF formulas with queries.
• scientific article; zbMATH DE number 4092808
• Exact learning of DNF formulas using DNF hypotheses

Cited in

(6)

• Implicitly preserving semantics during incremental knowledge base acquisition under uncertainty.
• Learning read-constant polynomials of constant degree modulo composites
• Proper learning of \(k\)-term DNF formulas from satisfying assignments
• Read-twice DNF formulas are properly learnable
• Learning Read-Constant Polynomials of Constant Degree Modulo Composites
• Learning unions of (1)-dimensional rectangles

This page was built for publication: On Learning Read-k-Satisfy-j DNF

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210120)