Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 16 Mars 2010

From Propositional Satisfiability to Quantified Boolean Formula

par Saïd Jabbour (INRIA-Microsoft, Saclay)

In the first part of this talk (SAT) we give an introduction to modern SAT solving, and then we present several contributions to Conflict Driven Clause Learning (CDCL), which is one of the key components of modern SAT solvers. This includes an extended implication graph containing additional arcs, called inverse arcs. These arcs are obtained by taking into account the satisfied clauses of the formula, which are usually ignored in classical conflict analysis. We also prove that the scope of clause learning can be enlarged by addressing other problems such as dynamic simplification of boolean formula. The second part describes two contributions on symmetry breaking in the QBF context. Finally, we highlight our research program on both SAT and QBF.

Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30