Joint CICLOPS-WLPE Workshop FloC-2010
associated with ICLP
CICLOPS is a series of colloquia on the implementation of constraint logic programming. Logic and Constraint programming is an important declarative programming paradigm. The features offered by this paradigm such as rule-basedness, pattern matching, automated backtracking, recursion, tabling, and constraint solving have been proved convenient for many programming tasks. Recent improvements in implementation technologies combined with advances in hardware and systems software have made logic and constraint programming a viable choice for many real-world problems.
WLPE is a series of workshops on practical logic-based software development methods and tools. Software plays a crucial role in modern society. While software keeps on growing in size and complexity, it is more than ever required to be delivered on time, free of error and meeting the most stringent efficiency requirements. Thus more demands are placed on the software developer, and consequently, the need for methods and tools that support the programmer in every aspect of the software development process is widely recognized. Logic plays a fundamental role in analysis, verification and optimization in all programming languages, not only in those based directly on logic. The use of logic-based techniques in software development is a very active area in computing; emerging programming paradigms and growing complexity of the properties to be verified pose new challenges for the community, while emerging reasoning techniques can be exploited.
CICLOPS-WLPE 2010 aims at bringing together, in an informal setting, people involved in research in the design and implementation of logic and constraint programming languages and systems and on logic-based methods and tools which support program development and analysis. In addition to papers describing more conceptual and theoretical work, papers describing the implementation of, and experience with, such tools will be welcome.
More information can be found here.
- Programming with Boolean Satisfaction
Michael Codish, Ben-Gurion University of the Negev (Israel)
In recent years, research on Boolean satisfiability (SAT) is generating remarkably powerful SAT solvers capable of handling larger and larger SAT instances. With the availability of progressively stronger SAT solvers, an accumulating number of applications have been developed which demonstrate that real world problems can often be solved by encoding them into SAT. One of the success stories is the application to termination analysis where we aim to automatically provide proofs of termination for software. Here, in the past five years, Boolean satisfiability has completely revolutionized the field.
One major obstacle in applying SAT solving to a given problem is to devise a suitable representation of the problem. This involves mapping the problem to a propositional formula in such a way that a model of the formula represents a solution of the original problem. This activity is just like programming (with logic): variables are Booleans and programs are formulas in conjunctive normal form. With expertise in declarative, logic and constraint programming, our community is well situated to join efforts in the development of new SAT encoding techniques and new applications for SAT solving. In this talk I will survey several SAT encoding techniques which come up in the application to termination analysis as well as in other applications.
- Solving Constraint Satisfaction Problems by a SAT Solver
Naoyuki Tamura, Kobe University (Japan)
(joint work with Tomoya Tanjo and Mutsunori Banbara, Kobe University, Japan)
A Boolean Satisfiability Testing Problem (SAT) is a combinatorial problem to find a Boolean variable assignment which satisfies all given Boolean formulas. Recent performance improvement of SAT technologies makes SAT-based approaches applicable for solving hard and practical combinatorial problems, such as planning, scheduling, hardware/software verification, and constraint satisfaction.
Sugar is a SAT-based constraint solver based on a new encoding method called order encoding which was first used to encode job-shop scheduling problems by Crawford and Baker. In the order encoding, a comparison x ≤ a is encoded by a different Boolean variable for each integer variable x and integer value a. The Sugar solver shows a good performance for a wide variety of problems, and became the winner of the GLOBAL categories in 2008 and 2009 CSP solver competitions.
The talk will provide an introduction to modern SAT solvers, SAT encodings, implementation techniques of the Sugar solver, and its performance evaluation.