1 |
The acquisition of the inflection systemAldridge, M. January 1988 (has links)
No description available.
|
2 |
Answer set programming with clause learningWard, Jeffrey Alan 30 September 2004 (has links)
No description available.
|
3 |
A linearized DPLL calculus with learningArnold, Holger January 2007 (has links)
This paper describes the proof calculus LD for clausal propositional logic,
which is a linearized form of the well-known DPLL calculus extended by clause
learning. It is motivated by the demand to model how current SAT solvers
built on clause learning are working, while abstracting from decision
heuristics and implementation details. The calculus is proved sound and
terminating. Further, it is shown that both the original DPLL calculus and
the conflict-directed backtracking calculus with clause learning, as it is
implemented in many current SAT solvers, are complete and proof-confluent
instances of the LD calculus. / Dieser Artikel beschreibt den Beweiskalkül LD für aussagenlogische Formeln in
Klauselform. Dieser Kalkül ist eine um Klausellernen erweiterte linearisierte
Variante des bekannten DPLL-Kalküls. Er soll dazu dienen, das Verhalten von
auf Klausellernen basierenden SAT-Beweisern zu modellieren, wobei von
Entscheidungsheuristiken und Implementierungsdetails abstrahiert werden soll.
Es werden Korrektheit und Terminierung des Kalküls bewiesen. Weiterhin wird
gezeigt, dass sowohl der ursprüngliche DPLL-Kalkül als auch der
konfliktgesteuerte Rücksetzalgorithmus mit Klausellernen, wie er in vielen
aktuellen SAT-Beweisern implementiert ist, vollständige und beweiskonfluente
Spezialisierungen des LD-Kalküls sind.
|
4 |
A linearized DPLL calculus with clause learning (2nd, revised version)Arnold, Holger January 2009 (has links)
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. / Viele formale Beschreibungen DPLL-basierter SAT-Algorithmen enthalten entweder nicht alle wesentlichen Beweistechniken, die in modernen SAT-Solvern implementiert sind, oder sind an bestimmte Heuristiken oder Datenstrukturen gebunden. Dies erschwert die Analyse beweistheoretischer Eigenschaften oder der Suchkomplexität derartiger Algorithmen. Mit diesem Artikel versuchen wir, diese Situation durch die Entwicklung eines nichtdeterministischen Beweiskalküls zu verbessern, der die Arbeitsweise von auf dem DPLL-Kalkül basierenden SAT-Algorithmen mit Klausellernen modelliert. Dieser Kalkül ist unabhängig von Implementierungsdetails, aber dennoch präzise genug, um eine formale Analyse realistischer DPLL-basierter SAT-Algorithmen zu ermöglichen.
|
Page generated in 0.0607 seconds