Conjunctions of unate DNF formulas: Learning and structure

DOI10.1006/INCO.1997.2684MaRDI QIDQ1383160zbMATH OpenOpenAlexFDO

Authors Aaron Feigelson, Lisa Hellerstein

Publication date 20 September 1998

Published in Information and Computation (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://semanticscholar.org/paper/1fd79c149934f9672d41a35a3bd48d06f7c60ec7

zbMATH Keywords

query learningBoolean formulas

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Recommendations

• Exact learning of DNF formulas using DNF hypotheses
• Learning with queries inside the class of unate \(k\)-quasi-Horn formulas
• Learnability of DNF with representation-specific queries
• Complexity theoretic hardness results for query learning

Cites work

• Exact learning Boolean functions via the monotone theory
• How many queries are needed to learn?
• Learning read-once formulas with queries
• Queries and concept learning

Cited in

(8)

• Learning a subclass of \(k\)-quasi-Horn formulas with membership queries
• Polynomial certificates for propositional classes
• Polynomial certificates for propositional classes.
• Learnability of quantified formulas.
• Algorithmic Learning Theory
• Learnability of solutions to conjunctive queries
• Learning with queries inside the class of unate \(k\)-quasi-Horn formulas
• A dichotomy theorem for learning quantified Boolean formulas

This page was built for publication: Conjunctions of unate DNF formulas: Learning and structure

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