New Developments in Symmetry Breaking in Search Using Computational Group Theory - Artificial Intelligence and Symbolic Computation - page 201

We denote the image of a literal ( X = α ) under a symmetry g by ( X = α ) g .
The set of all symmetries of a CSP form a group : that is, they are a collection of
bijections from the set of all literals to itself that is closed under composition of
mappings and under inversion. We denote the symmetry group of a CSP by G .
Note that under this definition of a symmetry, it is entirely possible to map a
partial assignment that does not violate any constraints to a partial assignment
which does. Suppose for instance that we had constraints ( X 1 #= X 2 ), ( X 2 #=
X 3 )whereeach X i had domain [ α, β ]. Then the symmetry group of the CSP
would enable us to freely interchange X 1 , X 2 and X 3 . However, this means that
we could map the partial assigment ( X 1 = α )

∧

( X 3 = β )(whichdoesnotbreak

either of the constraints) to ( X 1 = ( X 2 = β ) (which clearly does). This

shows that the interaction between symmetries and consistency can be complex.
There are various ways in which the symmetries of a CSP can act on the set
of all literals, we now examine these in more detail.

α ) ∧

Definition 3. A value symmetry ofaCSPisasymmetry g ∈ G such that if
( X = α ) g =( Y = β ) then X = Y .

The collection of value symmetries form a subgroup of G :thatis,thesetof
value symmetries is itself a group, which we denote by G

Val . We distinguish two

Val

types of value symmetries: a group G acts via pure value symmetries if for all

Val , whenever ( X = α ) g =( X = β ), we have ( Y = α ) g =( Y = β ). There
are CSPs for which this does not hold. However, at a cost of making distinct,
labelled copies of each domain we have the option to assume that

g ∈ G

G acts via

Val is pure then we may represent it as acting on the
values themselves, rather than on the literals: we write αg to denote the image
of α under g ∈ G

pure value symmetries. If G

Val .
We wish to define variable symmetries in an analogous fashion; however we
must be a little more cautious at this point. We deal first with the standard case.

Definition 4. Let L be a CSP for which all of the variables have the same
domains, and let G be the full symmetry group of L .A variable symmetry of L
is a symmetry g ∈ G such that if ( X = α ) g =( Y = β ) ,then α = β .

We need a slightly more general definition than this. Recall that if the value
group does not act via pure value symmetries, we make labelled copies of the
domains for each variable: afterwards we can no longer use Definition 4 to look
for variable symmetries, as the variables no longer share a common domain.
However, the domains of the variables do match up in a natural way. We describe
g ∈ G as being a variable symmetry if, whenever ( X = α ) g =( Y = β ), the values
α and β correspond to one another under this natural bijection. Formally, we
have the following definition.
Definition 5. Let L be a CSP with symmetry group G . Fix a total ordering on
D i for each i , and denote the elements of D i by α ij .A variable symmetry is a
symmetry g ∈ G such that if ( A i = α ij ) g =( A k = α kl ) then l = j .
That is, the original value and the image value have the same position in
the domain ordering. If all variables share a common domain then we recover