004 Datenverarbeitung; Informatik
Refine
Has Fulltext
- yes (111)
Year of publication
Document Type
- Article (102)
- Conference Proceeding (3)
- Doctoral Thesis (3)
- Master's Thesis (2)
- Preprint (1)
Is part of the Bibliography
- no (111) (remove)
Keywords
- Didaktik (13)
- Ausbildung (12)
- Hochschuldidaktik (12)
- Informatik (12)
- Computer Science Education (4)
- Competence Measurement (3)
- Secondary Education (3)
- Automatisches Beweisen (2)
- Big Data (2)
- Competence Modelling (2)
Institute
- Institut für Informatik und Computational Science (111) (remove)
Many formal descriptions of DPLL-based SAT algorithms either do not include all essential proof techniques applied by modern SAT solvers or are bound to particular heuristics or data structures. This makes it difficult to analyze proof-theoretic properties or the search complexity of these algorithms. In this paper we try to improve this situation by developing a nondeterministic proof calculus that models the functioning of SAT algorithms based on the DPLL calculus with clause learning. This calculus is independent of implementation details yet precise enough to enable a formal analysis of realistic DPLL-based SAT algorithms.