Theory and applications of satisfiability testing

This volume contains the papers presented at SAT 2009: 12th International Conference on Theory and Applications of Satis? ability Testing, held from June 30 to July 3, 2009 in Swansea (UK). The International Conference on Theory and Applications of Satis? ability Testing (SAT) started in 1996 as a series of workshops, and, in parallel with the growthof SAT, developedinto the main eventfor SAT research. This year’sc- ference testi? ed to the strong interest in SAT, regarding theoretical research,- searchonalgorithms, investigationsintoapplications, anddevelopmentofsolvers and software systems. As a core problem of computer science, SAT is central for many research areas, and has deep interactions with many mathematical s- jects. Major impulses for the development of SAT came from concrete practical applications as well as from fundamental theoretical research. This fruitful c- laboration can be seen in virtually all papers of this volume. There were 86 submissions (completed papers within the scope of the c- ference). Each submission was reviewed by at least three, and on average 4. 0 Programme Committee members. The Committee decided to accept 45 papers, consisting of 34 regular and 11 short papers (restricted to 6 pages). A main n- elty was a “shepherding process”, where 29% of the papers were accepted only conditionally, and requirements on necessary improvements were formulated by the ProgrammeCommittee and its installment monitored by the “shepherd” for thatpaper(using possibly severalroundsoffeedback).