ith apologies for multiple copies.

================================================================

Call for Papers and Participation

SymCon'04:

The Fourth International Workshop

on Symmetry and Constraint Satisfaction Problems

(http://www.dis.uu.se/SymCon04)

To be held at the Tenth International Conference

on Principles and Practice of Constraint Programming (CP 2004)

Toronto, Canada

27 September 2004

================================================================

INTRODUCTION

-------------

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.

WORKSHOP

--------

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

information

- 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

including:

- new

1. Final CFP: 4th International Workshop on Symmetry and Constraint

4. CFP: Symmetry and Constraints Workshop at CP 2004

5. CFP: SymCon'04: Workshop on Symmetry and Constraints

6. CFP: CP05 Workshop on Local Search in Constraint Satisfaction (LSCS 2005)

7. CFP: ASP2007 - 4th International Workshop on Answer Set Programming

8. CFP: VERIFY'07 - 4th International Verification Workshop

9. 2nd CFP: VERIFY'07 - 4th International Verification Workshop

11. CFP: Constraints Journal Special Issue on Symmetry in Constraint

1 post • Page:**1** of **1**