Learnability of quantified formulas.
From MaRDI portal
Publication:1426470
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
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.
