Finding all Solutions to a CNF. The DualSat SAT Solver

Elmar Stellnberger (Autor)

Buch | Softcover

72 Seiten

2021 | 21001 A. 1. Auflage
GRIN Verlag
978-3-346-41937-8 (ISBN)

Titel nicht im Sortiment

Artikel merken

Master's Thesis from the year 2020 in the subject Computer Science - Applied, grade: Sehr gut, Klagenfurt University (Institut für Angewandte Informatik), language: English, abstract: DualSAT is a performant new SAT-solver that is optimized to find and output all solutions to an input CNF usable by further processing steps that can follow. Solutions are stored as a number of disjoint solution classes that happen to be in Decomposable Negation Normal Form (DNNF).The solver implements new features like unentangled literal detection and backtracking with stack redo. Unentangled literal detection detects the remaining CNF to be in DNNF while a stack redo saves valuable work on conflict directed backjumps because much of the solver's stack content remains preserved. A combination of conflict dependent and independent heuristics ensures good results for known as well as novel and random CNFs. The dual data structures of DualSAT may also prove beneficial for new techniques with enhanced reasoning.

Erscheinungsdatum	17.10.2021
Sprache	englisch
Maße	148 x 210 mm
Gewicht	118 g
Themenwelt	Mathematik / Informatik ► Informatik
Schlagworte	CNF • conflict independent heuristic • conflictindependentheuristic • Decomposable Negation Normal Form • DecomposableNegationNormalForm • dual datastructures • dualdatastructures • enhanced reasoning • enhancedreasoning • model counting • modelcounting • non-linear optimization • Non-linearoptimization • progress saving • progresssaving • #SAT • SAT-solver
ISBN-10	3-346-41937-1 / 3346419371
ISBN-13	978-3-346-41937-8 / 9783346419378
Zustand	Neuware