Learnability of quantified formulas.

DOI10.1016/S0304-3975(03)00342-6zbMath1060.68049OpenAlexW2170491051MaRDI QIDQ1426470

Peter G. Jeavons, Victor Dalmau

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)

Related Items (9)

Hard constraint satisfaction problems have hard gaps at location 1 ⋮ Learning intersection-closed classes with signatures ⋮ Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights ⋮ On the non-efficient PAC learnability of conjunctive queries ⋮ Varieties with few subalgebras of powers ⋮ A new tractable class of constraint satisfaction problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The expressive rate of constraints

Cites Work

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

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