×

zbMATH — the first resource for mathematics

Improving SAT algorithms by using search pruning techniques. (English) Zbl 1067.68650
Walsh, Toby (ed.), Principles and practice of constraint programming - CP 2001. 7th international conference, Paphos, Cyprus, November 26 – December 1, 2001. Proceedings. Berlin: Springer (ISBN 3-540-42863-1). Lect. Notes Comput. Sci. 2239, 770 (2001).
Summary: Propositional Satisfiability (SAT) is fundamental in solving many application problems in Artificial Intelligence and in other fields of Computer Science and Engineering. In the recent past, intelligent backtrack search algorithms for SAT have empirically been shown to be highly effective in pruning the amount of search, by applying strategies for non-chronological backtracking and procedures for clause recording. Apart from the commonly used pruning techniques, these algorithms can be augmented with other different techniques, namely identification of necessary assignments, randomized strategies and simplification techniques.
For the entire collection see [Zbl 0984.00059].

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDF BibTeX XML Cite
Full Text: Link