SymCon'09

The Ninth International Workshop on Symmetry and Constraint Satisfaction Problems

A Satellite Workshop of CP 2009 - September 20, 2009 - Lisbon, Portugal

Program Important Dates Call for Papers Organization Previous SymCon Workshops

*Submission Information*

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.



Symcon'09 Program

(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

Invited Speaker: Pierre Flener, Uppsala University, Sweden.

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.

Important Dates



Call for Papers(CFP in text format)

Workshop Description

SymCon'09 is the 9th in a series of workshops affiliated with the CP conference, and focuses on the investigation of symmetry and symmetry breaking techniques for Constraint Satisfaction Problems (CSPs). 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.

Workshop topics include, but are not limited to:

Attendance

The workshop is open to all members of the CP community. At least one author of each submission accepted for presentation must attend the workshop and present the contribution. All workshop attendees must pay the CP registration fee in addition to the workshop fee.

Paper Submission

To submit a paper to the workshop, please e-mail a PS or PDF file in IJCAI style to symcon09@gmail.com

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.

Selection Process

All submissions will be reviewed. Those that present a significant contribution to the workshop topics will be accepted for publication in the workshop proceedings. The proceedings will be available electronically at the workshop web-page and in hardcopy at CP 2009. If necessary, for time reasons, only a subset of the papers will be presented. A selection will then be made by the Program Committee Chairs.

Organization

Workshop Organizers

Programme Committee Members