Constraint acquisition is formulated as a concept learning task.
In constraint satisfaction there are dependencies amongst the atomic variables, while in conjunctive concepts they are pairwise independent.

[A SAT-Based Version Space Algorithm for Acquiring Constraint Satisfaction Problems] 2003
Constraint Acquisition(CONACQ)
SAT based Version space algorithm for acquiring constraint satisfaction problems from examples of solutions and non-solutions of a target problem.
Each constraint specifies a restriction on some set of variables.

Goal:
The learner is to induce a constraint network that uses combinations of constraints defined from the library 
and that is consistent with the solutions and non-solutions provided by the user.

Based on the paradigm of version space learning considering Version space learning as a Satisfiability problem.

Any example is encoded as a set of clauses using as atoms the constraint vocabulary defined from the library, 
and any model of the resulting satisfiability problem captures an admissible constraint network for the corresponding acquisition problem.

-Any SAT solver can be used as a basis for version space learning
-SAT concepts such as Unit propagation and Backbone detection can be used to improve learning rate
-Any domain specific knowledge can be used to improve the quality of the acquired network

Constraint Library: Collection B of binary constraints

Assumption:
The set of variables and the set of domain values are finite, pre-fixed and known to the learner(known as Vocabulary (X,D) common to both learner and user)
Constraint library from which it can build and compose constraints
Every constraint from the library is binary(can be extended over higher arity)

Input:
Constraint Library B
Training set consists of a pair (E+,E-) of sets of examples

Output:
A set of clauses (A constraint network that consists of a set of variables, a set of domain values and a set of constraints)

A constraint network C is said to be admissible for a library B if for each constraint c in C there exists a set of constraints b in B such that c can be expressed as a conjunction of b. 

Problem Statement:
To find an appropriate combination of constriants that is consistent with the examples provided by the user

Binary constraint: A tuple c = (var(c),rel(c)) where var(c) is a pair of variables in X and rel(c) is a binary relation defined on D
var(c): scope of the the constraint c
rel(c): relation of constraint c

The version space of a constraint acquisition problem is the set of all constraint networks 
that are admissible for the given library and that are consistent with the given training set.

A clause is a disjunction of literals, and a clausal theory is a conjunction of clauses.

[Query-driven Constraint Acquisition] 2010
A query is essentially a complete instantiation of values to the variables in the constraint 
network that the user must classify as either a solution or nonsolution of her ‘target’ network.

In the classic query generation strategy, regardless of the classification of the query, the size of the version space is reduced by half. 
Therefore, convergence of the version space can be achieved using a logarithmic number of queries.
When acquiring constraint networks, query generation becomes NP-hard.

In constraint acquisition, while the ordering over the hypothesis space is most naturally defined in terms of the solution space of constraint networks, we usually learn at the constraint level.
i.e. a compact representation of the set of solutions of a hypothesis.

In practice, it can be the case that an example e from the training set does not bring any more information than that 
which has already been provided by the other examples that have been considered so far.

Redundant and Irredundant queries
Different irredundant examples give us different gains in knowledge.
The gain for a query q is directly related to the size of |k(q)[K]| and its classification f(q).
If it is a positive example, k unary negative clauses will be added to K and allows the set of literals to 0.
If it is a negative example, a positive clause of size k is added to K, thus removing 1/2k models.

Therefore, an optimistic query is maximally informative if it is classified as positive it sets all literals it introduces to 0.
If it is classified as negative it is minimally informative.

The optimal query strategy is one that involves proposing a query that will reduce the size of the version space in half regardless of how the user classifies it.

A positive clause represents the set of constraints that reject a negative example already processed by CONACQ.
At least one of the constraints in such a set L rejects an instance.
Choosing the smallest one increases the chances to quickly converge on a unary clause.
CONACQ is implemented using SAT4J and Choco.