Polynomial certificates for propositional classes

DOI10.1016/J.IC.2006.03.001MaRDI QIDQ2495655zbMATH OpenOpenAlexFDO

Authors Marta Arias, Aaron Feigelson, Roni Khardon, Rocco A. Servedio

Publication date 30 June 2006

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

Full work available at URL https://doi.org/10.1016/j.ic.2006.03.001

zbMATH Keywords

monotone expressions in Conjunctive Normal Form

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Recommendations

• Polynomial certificates for propositional classes.
• Exact learning: on the boundary between Horn and CNF
• Conjunctions of unate DNF formulas: Learning and structure
• Exact learning of DNF formulas using DNF hypotheses
• scientific article; zbMATH DE number 1263194

Cites work

• A theory of the learnable
• Algorithmic Learning Theory
• Conjunctions of unate DNF formulas: Learning and structure
• Exact learning of DNF formulas using DNF hypotheses
• First-order \(jk\)-clausal theories are PAC-learnable
• How many queries are needed to learn?
• scientific article; zbMATH DE number 1104356 (Why is no real title available?)
• scientific article; zbMATH DE number 1453030 (Why is no real title available?)
• Inductive Logic Programming
• Knowledge compilation and theory approximation
• Learnability and the Vapnik-Chervonenkis dimension
• Learning closed Horn expressions
• Learning conjunctions of Horn clauses
• Learning function-free Horn expressions
• Learning to reason with a restricted view
• Logical settings for concept-learning
• On sentences which are true of direct unions of algebras
• Polynomial certificates for propositional classes.
• Queries and concept learning
• Queries revisited.
• Reasoning with models
• The decision problem for some classes of sentences without quantifiers

Cited in

(5)

• Directed hypergraphs and Horn minimization
• Query Learning and Certificates in Lattices
• Canonical Horn representations and query learning
• Construction and learnability of canonical Horn formulas
• Polynomial certificates for propositional classes.

This page was built for publication: Polynomial certificates for propositional classes

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