Learnability of relatively quantified generalized formulas

DOI10.1007/978-3-540-30215-5_28MaRDI QIDQ5464509zbMATH OpenOpenAlexFDO

Authors Andrei A. Bulatov, Hubie Chen, Víctor Dalmau

Publication date 18 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b100989

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Recommendations

• Learnability of quantified formulas.
• A dichotomy theorem for learning quantified Boolean formulas
• Boolean formulas are hard to learn for most gate bases
• Complexity theoretic hardness results for query learning
• Conjunctions of unate DNF formulas: Learning and structure

Cited in

(12)

• Relatively quantified constraint satisfaction
• Learnability of quantified formulas.
• A dichotomy theorem for learning quantified Boolean formulas
• Learning a propagation complete formula
• Complexity parameters for first order classes
• Learning a representation for optimizable formulas
• Boolean formulas are hard to learn for most gate bases
• Learnability of solutions to conjunctive queries
• The Myth of Generic DPA…and the Magic of Learning
• Learnability and definability in trees and similar structures
• The expressive rate of constraints
• Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights

This page was built for publication: Learnability of relatively quantified generalized formulas

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