CFP: 4th International Workshop on Symmetry and Constraint Satisfaction

CFP: 4th International Workshop on Symmetry and Constraint Satisfaction

Post by ianm » Fri, 04 Jun 2004 01:00:09

ith apologies for multiple copies.

Call for Papers and Participation


The Fourth International Workshop
on Symmetry and Constraint Satisfaction Problems

To be held at the Tenth International Conference
on Principles and Practice of Constraint Programming (CP 2004)

Toronto, Canada
27 September 2004



A symmetry is a transformation of an entity which preserves the
properties of the entity. The transformed entity is thus
identical to and indistinguishable from the original entity. For
instance, rotating a chess board 180 degrees gives us a board
which is indistinguishable from the original board.

Many constraint satisfaction problems (CSPs) have symmetries in
the variables, domains or constraints - or any combination
thereof. Each of these symmetries preserve satisfiability, so that
when there is symmetry in a CSP, any assignment can be transformed
into an equivalent assignment without affecting whether or not it
satisfies the constraints. Similarly, applying such a
transformation to a partial assignment does not affect whether or
not it can be extended to an assignment satisfying the
constraints. For instance, in many CSPs some of the variables
refer to entities which are indistinguishable, and the values
assigned to these variables can be interchanged in any solution.

Symmetry increases the combinatorial complexity of CSPs. In the
presence of symmetry, a constraint solver may waste a large amount
of time considering symmetric but equivalent assignments or
partial assignments. Hence, dealing with symmetry is often
crucial to the success of solving such CSPs efficiently.

As well as exploiting symmetry when solving CSPs, CSP solving
techniques have been used to solve symmetry-related problems. For
example, they have been used to answer the question of whether a
particular search state is symmetrically equivalent to one already
explored. As another example, they have been used to derive
"generators" of a symmetry group, which allow the symmetries to be
represented effectively without the need to list them all
explicitly. Constraint programming techniques have the potential
to improve on existing algorithms for solving these and related
group-theoretic problems.


SymCon'04 will be the fourth workshop in the series, following the
successful earlier workshops SymCon'01 at CP 2001 in Paphos
(Cyprus), SymCon'02 at CP 2002 in Ithaca (U.S.A.), and SymCon'03
at CP 2003 in Kinsale (Ireland). It will be a full-day workshop.

Workshop topics include (but are not limited to):

- symmetry detection

- exploitation of symmetry, e.g. heuristics which use symmetry

- elimination of symmetry, e.g. remodelling the problem or adding
constraints to reduce symmetry

- avoidance of symmetry, e.g. algorithms which avoid considering
assignments symmetric to any assignment already considered

- exploitation of mathematical techniques such as group theory for
dealing with symmetry in CSPs

- application of CSPs to symmetry and related algebraic problems

The workshop will provide a forum for research into any of these topics

- new