To start with we give an abstract definition of a constraint language. According to [Höhfeld and Smolka1988] a constraint is some piece of syntax constraining the values of the variables occurring in it, i.e., which denotes a set of assignments for these variables relative to a given interpretation.
The following definitions are all made with respect to some given constraint language.
A constraint is satisfiable if there exists at least one interpretation in which has a solution. A constraint is valid in an interpretation if every -assignment is a solution of in , i.e., if I = ASSI. An interpretation satisfies a constraint if is valid in . An interpretation is a model of a set of constraints if it satisfies every constraint in .
The subsumption preordering on sets of constraints and the corresponding equivalence relation is defined as follows (following the notation of [Dörre1993]):
A variable renaming is a bijection VAR VAR that is the identity except for finitely many exceptions. If is a renaming, a constraint is called a -variant of a constraint if
for every interpretation ( denotes the functional composition of both functions). A constraint is called a variant of a constraint if there exists a renaming such that is a -variant of . Note that renaming is homomorphic with respect to the subsumption relation, thus it does not affect the subsumption ordering of constraints (see proposition 2.2 in [Höhfeld and Smolka1988]).
A constraint language is closed under renaming if every constraint has a -variant for every renaming . A constraint is closed under intersection if for every two constraint and there exists a constraint such that I 'I = I for every interpretation .
A constraint language is decidable if the satisfiability of its constraints is decidable. In section 3.2.2 we present a decidable constraint language.
A constraint language is compact if for every set of constraints holds: is satisfiable iff every finite subset of is satisfiable.
Before we present in section 3.2.2 the constraint language to be used in this thesis we present the relational extension of constraint languages.