Logic List Mailing Archive

CfP Special issue of "Constraints Journal" on 'Symmetry in Constraint Programming'

CALL FOR PAPERS

                      Constraints Journal

       Special Issue on Symmetry in Constraint Programming


GUEST EDITORS

Ian Gent, University of St Andrews, U.K.
Jean-Francois Puget, ILOG, France.
Barbara Smith, Cork Constraint Computation Centre, Ireland.

INTRODUCTION

Many constraint satisfaction problems have some symmetry: any
assignment can be transformed into a set of symmetrically equivalent
assignments.  The symmetries preserve solutions, so that if any
assignment in a symmetry equivalent class is consistent with the
constraints, they all are.  For instance, in many CSPs some of the
variables refer to entities that are indistinguishable, and the values
assigned to these variables can be interchanged in any solution.
Where symmetry exists in a CSP, dealing with it effectively is often
critical to the success of solving the CSP.  Unless this is done,
search often thrashes, revisiting symmetrically equivalent states over
and over again.  CSP solving techniques have also been used to solve
symmetry-related problems.  For instance, they have been used to
answer the question of whether a particular search state is
symmetrically equivalent to one already explored.  Constraint
programming techniques have the potential to improve on existing
algorithms for solving similar group-theoretic problems.

Symmetry in constraint programming has been an active area of research
for several years, and much significant work has not yet appeared in
journals.  To rectify this, papers are solicited for a special issue
of the Constraints Journal.  Papers on any aspect of symmetry in
constraint programming are welcome, including:
      * symmetry detection
      * exploitation of symmetry e.g. heuristics which use symmetry
        information
      * elimination or avoidance of symmetry e.g. by remodelling the
        problem, adding constraints, or modifying the search algorithm
      * exploitation of mathematical techniques such as group theory
      * applications of constraint programming to problems with symmetry.

PAPER SUBMISSION

Researchers are invited to submit original papers that make a
significant contribution to the field to
constraints-symmetry@dcs.st-and.ac.uk.  (Note that the usual on-line
submission procedure for the Constraints journal will not be followed
initially for the Special Issue).  All submissions should be in .pdf
format and follow Constraints Journal guidelines. Papers are expected
to be about 20-25 journal pages.

When submitting, please use the subject "Constraints Special Issue
Paper Submission" and clearly specify the e-mail address and phone
number of the corresponding author.  Receipt of papers will be
acknowledged.  Submissions will be reviewed by at least two reviewers.
All accepted papers will meet the usual high-quality standards of the
Constraints Journal.

Intending authors should send an expression of interest (including a
provisional title, list of authors and a few sentences outlining the
topic of the paper) to constraints-symmetry@dcs.st-and.ac.uk by the
end of June, 2006.

IMPORTANT DATES

Expression of interest: end of June, 2006
Submission of papers: end of September, 2006
Notification of acceptance: end of December, 2006
Final versions of accepted papers: end of February, 2007
Expected publication of the Special Issue: mid-2007

Special issue homepage:
http://www.dcs.st-and.ac.uk/~ipg/symmetry
Constraints Journal homepage:
http://ai.uwaterloo.ca/~vanbeek/Constraints/constraints.html