Learnability of quantified formulas.

DOI10.1016/S0304-3975(03)00342-6MaRDI QIDQ1426470zbMATH OpenOpenAlexFDO

Authors Víctor Dalmau, P. Jeavons

Publication date 14 March 2004

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(03)00342-6

zbMATH Keywords

ClonesComputational learningQuantified formulas

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Recommendations

• Algorithmic Learning Theory
• A dichotomy theorem for learning quantified Boolean formulas
• scientific article; zbMATH DE number 1453047
• Learnability of solutions to conjunctive queries
• Conjunctions of unate DNF formulas: Learning and structure

Cites work

• A dichotomy theorem for learning quantified Boolean formulas
• A theory of the learnable
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
• Characterising tractable constraints
• Closure properties of constraints
• Constraints, consistency and closure
• Cryptographic limitations on learning Boolean formulae and finite automata
• Exact learning Boolean functions via the monotone theory
• Group-theoretic algorithms and graph isomorphism
• scientific article; zbMATH DE number 3162893 (Why is no real title available?)
• scientific article; zbMATH DE number 3972929 (Why is no real title available?)
• scientific article; zbMATH DE number 3972930 (Why is no real title available?)
• scientific article; zbMATH DE number 3987347 (Why is no real title available?)
• scientific article; zbMATH DE number 4029649 (Why is no real title available?)
• scientific article; zbMATH DE number 54155 (Why is no real title available?)
• scientific article; zbMATH DE number 1061261 (Why is no real title available?)
• scientific article; zbMATH DE number 3227055 (Why is no real title available?)
• Inductive Logic Programming: Theory and methods
• Learning conjunctions of Horn clauses
• Learning counting functions with queries
• Polynomial interpolation and the Chinese remainder theorem for algebraic systems
• Prediction-preserving reducibility
• Queries and concept learning
• The complexity of satisfiability problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Tractable constraints on ordered domains
• When won't membership queries help?

Cited in

(16)

• A new tractable class of constraint satisfaction problems
• A dichotomy theorem for learning quantified Boolean formulas
• Learning a propagation complete formula
• Learning intersection-closed classes with signatures
• Varieties with few subalgebras of powers
• Learning a representation for optimizable formulas
• The subpower membership problem for finite algebras with cube terms
• scientific article; zbMATH DE number 2086423 (Why is no real title available?)
• Learnability of solutions to conjunctive queries
• Algorithmic Learning Theory
• On the non-efficient PAC learnability of conjunctive queries
• The subpower membership problem of 2-nilpotent algebras
• Learnability and definability in trees and similar structures
• The expressive rate of constraints
• Hard constraint satisfaction problems have hard gaps at location 1
• Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights

This page was built for publication: Learnability of quantified formulas.

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