SymCon'04: THE 4TH INTERNATIONAL WORKSHOP ON SYMMETRY AND CONSTRAINT SATISFACTION PROBLEMS . A Satellite Workshop of CP'2004 (Tenth International Conference on Principles and Practice of Constraint Programming) . 27 September 2004 , Toronto, Canada.

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. The SymCon'04 workshop will provide a forum for research into any aspect of symmetry and CSPs. It 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). URL: http://zeynep.web.cs.unibo.it/SymCon04/