Symmetries occur frequently in CSPs. When undetected, they cause thrashing during traditional backtracking search by redundantly exploring symmetric parts of the search space. The topic was discussed as far back as 1874 by Glaisher, and new techniques to detect and/or break symmetry have been proposed in recent years. However, many outstanding problems remain. For instance, the detection and exploitation of local, dynamic, and weak forms of symmetry remains a challenge.

The workshop is a forum for researchers to present advances in symmetry breaking techniques and to discuss the above or other open problems. Additionally, the workshop welcomes the presentation of applications and case studies that exhibit some form of symmetry. The workshop is relevant to the computational group theory (CGT) community because CGT is often the theory underlying many symmetry breaking techniques. Importantly, the organizers welcome submissions from researchers working in other areas of Artificial Intelligence who feel that their work would be of interest to the CP community. Such areas include planning, model checking, QBF formulas, finite model search, and theorem proving in FOL.

(papers will be available soon)

10:30-11:00 | B. Benhamou, T. Nabhani, R. Ostrowski, and M.R,. Saidi - Dynamic symmetry detection and elimination for the satisfiability problem. |

11:00-11:30 | Katsirelos and T. Walsh - Symmetries of symmetry breaking constraints |

11:30-12:30 | Invited Speaker: Pierre Flener, Uppsala University, Sweden. (see abstract) |

12:30-2:00 | Lunch |

2:00-2:30 | G. Katsirelos, N. Narodytska, and T. Walsh - Breaking generator Symmetry |

2:30-3:00 | C. Appold - Using state symmetries to speed up symmetry reduction in model checking. |

3:00-3:30 | T. Januschowski, B.M. Smith, and M.R.C. van Dongen - Foundations of symmetry breaking revisited. |

3:30-4:00 | Break |

4:00-4:30 | S.D. Prestwich, B. Hnich, H. Simonis, R. Rossi, and S.A. Tarim - Boosting partial symmetry breaking by local search |

4:30-5:00 | Discussion and Closing |

*Abstract*

**Structural Symmetry Handling**

I summarise the main results of the CORSA project between Uppsala University (Sweden) and Brown University (USA). Our goal was to identify classes of combinatorial problems that are practically relevant and for which symmetry detection and symmetry breaking are tractable, i.e., polynomial in time and space. By exploiting the structure of these classes of combinatorial problems, we devised dedicated symmetry-breaking search procedures and dominance detection schemes, as well as symmetry-breaking constraints and a symmetry detection scheme. Joint work with Justin Pearson, Meinolf Sellmann, Pascal Van Hentenryck, and Magnus Ågren.

~~Submission deadline: 31 July 2009 (extended)~~~~Notification of acceptance: 14 August 2009~~~~Camera ready deadline: 26 August 2009~~- Workshop: Sunday, 20th September 2009

- Symmetry definition: semantic symmetry, syntactic symmetry, constraint symmetry, solution symmetry
- Automatic symmetry detection: static approaches and dynamic approaches
- Global symmetry detection and elimination
- Dynamic symmetry detection and elimination
- Combining symmetry breaking techniques
- Exploiting weak forms of symmetries like "dominance" and "almost
- symmetries"
- Case studies of problems that exhibit interesting symmetries
- Application of computational group theory techniques to symmetry breaking
- Heuristics that use information about symmetry to guide search - Elimination and avoidance of symmetry by re-modelling
- Dynamic avoidance of symmetric states during search
- Complexity analysis of symmetry breaking techniques
- Application of CSPs to symmetry and related algebraic problems - Comparing symmetry breaking techniques in constraint programming with techniques for dealing with symmetry in other search domains
- Symmetry in CNF formulas and OBF formulas
- Symmetry in finite model search in first order logic
- Novel exploitation of symmetry in varied search domains of interest to the CP community

Papers must be formatted using IJCAI requirements (see formatting requirements here), and can be of any length not exceeding 8 pages. All submissions must be received by July 31, 2009. The Program Committee Chairs will acknowledge all submissions. If a submitted paper is not acknowledged in 2 working days, the authors are kindly requested to contact one of the chairs.

Workshop Organizers

- Alex Fukunaga, Tokyo Institute of Technology, Chair
- Belaïd Benhamou, Université de Provence (Aix-Marseille I), co-Chair
- Meinolf Sellmann, Brown University, co-Chair

- Fadi A. Aloul, American University of Sharjah, U.A.E.
- Berthe Y. Choueiry, University of Nebraska-Lincoln Lincoln, USA
- Pierre Flener, Uppsala University, Sweden
- Alan Frisch University of York, UK
- Brahim Hnich, Izmir University of Economics Sakarya Caddesi, Izmir, Turkey
- Zeynep Kiziltan, University of Bologna, Italy
- Ines Lynce, Instituto Superior Tecnico INESC-ID Lisboa, Portugal
- Francois Margot Carnegie Mellon University, USA
- Pedro Meseguer, Universitat Autonoma de Barcelona, Spain.
- Justin Pearson, Uppsala University, Sweden
- Karen Petrie, Oxford University, UK
- Steve Prestwich, University College Cork, Ireland
- Lakhdar Sais, Universite d'Artois, France.
- Pierre Siegel, Universite of Provence, Aix-Marseille I, France.
- Pascal van Hentenryck, Brown University, U.S.A.
- Toby Walsh, University of New South Wales, Australia
- Jian Zhang, Institute of Software Chinese Academy of Sciences, Beijing, China