Extending the Reach of SAT with Many-Valued Logics

✍ Scribed by Ramón Bejar; Alba Cabiscol; Cesar Fernández; Felip Manyà; Carla Gomes

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 197 KB
• Volume: 9
• Category: Article
• ISSN: 1571-0653
• DOI: 10.1016/s1571-0653(04)00336-1

✦ Synopsis

We present Regular-SAT, an extension of Boolean Satisfiability based on a class of many-valued CNF formulas. Regular-SAT shares many properties with Boolean SAT, which allows us to generalize some of the best known SAT results and apply them to Regular-SAT. In addition, Regular-SAT has a number of advantages over Boolean SAT. Most importantly, it produces more compact encodings that capture problem structure more naturally. Furthermore, its simplicity allows us to develop Regular-SAT solvers that are competitive with SAT and CSP procedures. We present a detailed performance analysis of Regular-SAT on several benchmark domains. These results show a clear computational advantage of using a Regular-SAT approach over a pure Boolean SAT or CSP approach, at least on the domains under consideration. We therefore believe that an approach based on Regular-SAT provides a compelling intermediate approach between SAT and CSPs, bringing together some of the best features of each paradigm.