Refine
Has Fulltext
- yes (3)
Document Type
- Article (1)
- Part of Periodical (1)
- Preprint (1)
Is part of the Bibliography
- no (3)
Keywords
- Automatisches Beweisen (2)
- DPLL (2)
- Klausellernen (2)
- SAT (2)
- Automated Theorem Proving (1)
- Clause Learning (1)
- Logikkalkül (1)
- automated theorem proving (1)
- clause learning (1)
- logical calculus (1)
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.
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.
Wissenschaftliche Artikel: Sabine Boehlich “Nisters Nay-gayst. Der Schriftsteller als Zaddik” Juliane Rösch „Di berliner hobn nisht gegloybt zeyere oygn“. Das jiddischsprachige Theater GOSET und der Regisseur Alexander Granovsky Anne-Christin Saß „Wenn die Nazi-Verbrecher nach Hause kommen” – Dovid Eynhorns Berichte über die nationalsozialistischen Verbrechen im New Yorker Forverts 1940-1945 Rebekka Denz Der „Froyenvinkl“ : Die Frauenrubrik in der bundischen Tageszeitung „Naye Folkstsaytung“ Nathanael Riemer Some parallels of stories in Glikls of Hameln Zikhroynes Jiddisch aus aller Welt: Holger Nath The First Yiddish Summer Program in Birobidzhan (August 13-August 30, 2007) Satoko Kamoshida A woman and a language: In the case of a Yiddish speaker in Israel Arturo Kerbel “Dear brother! Where from are you coming?” A brief history of the Yiddish language and culture in Mexiko Kazuo Ueda Jiddischforschung in Japan Essay: Elvira Grözinger Die Deutsche Bahn und die Krux mit dem Gedenken Tagungsberichte: “Zwischenräume”. Jüdisch-christliche Lebenswelten unter venezianischer Herrschaft im späten Mittelalter und der frühen Neuzeit. Venedig, Deutsches Studienzentrum und Dipartimento di Studi Storici der Universität Ca’ Foscari, 5.9.-7.9. 2007. (Daniel Jütte) “Global Forum for Combating Antisemitism”, Israelisches Außenministerium, Jerusalem, 24.-25.2. 2008. (Clemens Heni) Rezensionen: Arno Herzig/Cay Rademacher (Hg.): Die Geschichte der Juden in Deutschland (Robert Jütte) Georg Bossong: Die Sepharden. Geschichte und Kultur der spanischen Juden (Rafael Arnold) Barbara Staudinger: Die jüdische Welt und die Wittelsbacher (Daniel Jütte) Leon Modena: Jüdische Riten, Sitten und Gebräuche. Hg., übersetzt und kommentiert von Rafael Arnold (Karl E. Grözinger) Kenneth Stow: An Image and Its Interpreters. Continuity in the Catholic-Jewish Encounter (Elvira Grözinger) Aldina Quintana Rodríguez: Geografía Lingüística del Judeoespañol. Estudio sincrónico y diacrónico (Rafael Arnold) Wolfgang Vogt: Moses Mendelssohns Beschreibung der Wirklichkeit menschlichen Erkennens (Grazyna Jurewicz) Stefan Müller-Doohm (Hg.): Adorno-Portraits. Erinnerungen von Zeitgenossen (Michael Dallapiazza) Andrea Löw: Juden im Getto Litzmannstadt. Lebensbedingungen, Selbstwahrnehmung, Verhalten. Die Chronik des Gettos Lodz/Litzmannstadt. Hg. v. Sascha Feuchert, Erwin Leibfried, Jörg Riecke (Maria Kühn-Ludewig) Eglè Bendikaitè: Sionistinis sajudis Lietuvoje. Litauisches Historisches Institut (Elvira Grözinger) Barbara Staudinger (Hg.): Von Bayern nach Erez Israel. Auf den Spuren jüdischer Volkskunst. From Bavaria to Eretz Israel. Tracing Jewish Folk Art (Anat Feinberg) Hugh Denman (Hg.): Isaac Bashevis Singer: His Work and His World (Elvira Grözinger) Annkatrin Dahm: Der Topos der Juden. Studien zur Geschichte des Antisemitismus im deutschsprachigen Musikschrifttum (Daniel Jütte) Max Peter Baumann/Tim Becker/Raphael Woebs (Hg.): Musik und Kultur im jüdischen Leben der Gegenwart (Joel E. Rubin)