Information Technology Reference
In-Depth Information
Definition 4 from Definition 5. Note that in the above definition, we may order
at least one domain arbitrarily without affecting whether or not a symmetry is
deemed to be a variable symmetry: it is the
relative ordering
of the domains
that is crucial.
There may be several possible orderings of the domains, corresponding to
different choices of variable group: the value group is often a normal subgroup
of
G
(see section 3), and hence is uniquely determined, but there will usually
be several (conjugate) copies of the variable group, corresponding to distinct
split extensions. If there is a unique copy of the variable group, as well as a
unique copy of the value group, then
G
is the direct product of these two normal
subgroups. However, in the current context, ordering any one domain induces
a natural order on all of the remaining domains. This is because our variables
either have a common domain, or originally had a common domain which has
now been relabelled into several distinct copies (one for each variable).
The collection of all variable symmetries (for a given ordering on each do-
main) is a subgroup of
Var
. We define a
pure variable
symmetry
to be a variable symmetry such that if (
A
i
G
, which we denote
G
=
α
ij
)
g
=(
A
k
=
α
kj
)
then the value of
k
does not depend on
j
.
1.2 GE-Trees
In [10] we introduced the GE-tree, a search tree
T
foraCSP
L
with the property
that searching
T
finds exactly one representative of each equivalence class of
solutions under the symmetry group of
L
. Before we can define a GE-tree, we
need a few more group-theoretic and search-based definitions.
We consider only search strategies in which all allowed options for one vari-
able are considered before any values for other variables. This is a common,
although not universal, pattern in constraint programming. Therefore, we con-
sider search trees to consist of nodes which are labelled by variables (except for
the leaves, which are unlabelled), and edges labelled by values. We think of this
as meaning that the variable is set to that value as one traverses the path from
the root of the tree toward the leaves. At a node
, the partial assignment given
by reading the labels on the path from the root to
N
N
(ignoring the label at
N
itself) is the
state
at
. We will often identify nodes with their state, when the
meaning is clear. By the
values in
N
N
we mean the values that occur in literals
in the state at
) similarly for
variables. We will often speak of a permutation as mapping a node
N
, we denote this set by Val(
N
). We define Var(
N
N
to a node
M
, although strictly speaking the permutation maps the literals in the state at
N
to the literals in the state at
M
(in any order).
Definition 6.
Let
G
be a group of symmetries of a CSP. The
stabiliser
of a
literal
(
X
=
α
)
is the set of all symmetries in
G
that map
(
X
=
α
)
to itself.
This set is itself a group. The
orbit
of a literal
(
X
=
α
)
,denoted
(
X
=
α
)
G
,is
the set of all literals that can be mapped to
(
X
=
α
)
by a symmetry in
G
. That
is
(
X
=
α
)
G
:=
{
(
Y
=
β
):
∃g ∈ Gs.t.
(
Y
=
β
)
g
=(
X
=
α
)
}.
The orbit of a node is defined similarly.
Search WWH ::
Custom Search