On subsumption removal and on-the-fly CNF simplification

LINTAO, ZHANG

In: Theory and applications of satisfiability testing (St Andrews, 19-23 June 2005)Lecture notes in computer science :482-489

Konferenz - print, 12 ref

Wie komme ich dran?

CNF Boolean formulas generated from resolution or solution enumeration often have much redundancy. Efficient algorithms are needed to simplify and compact such CNF formulas. In this paper, we present a novel algorithm to maintain a subsumption-free CNF clause database by efficiently detecting and removing subsumption as the clauses are being added. We then present an algorithm that compact CNF formula further by applying resolutions to make it Decremental Resolution Free. Our experimental evaluations show that these algorithms are efficient and effective in practice.

Titel:	On subsumption removal and on-the-fly CNF simplification
Autor/in / Beteiligte Person:	LINTAO, ZHANG
Link:	E-Journal im Bestand der UB Hagen? View record from PASCAL Archive
Quelle:	Theory and applications of satisfiability testing (St Andrews, 19-23 June 2005)Lecture notes in computer science :482-489
Veröffentlichung:	Berlin: Springer, 2005
Medientyp:	Konferenz
Umfang:	print, 12 ref
ISSN:	0302-9743 (print)
Schlagwort:	Computer science Informatique Sciences exactes et technologie Exact sciences and technology Sciences appliquees Applied sciences Informatique; automatique theorique; systemes Computer science; control theory; systems Informatique théorique Theoretical computing Fonctions logiques, booléennes et de commutation Logical, boolean and switching functions Base donnée Database Base dato Enumération Enumeration Enumeración Formule CNF Conjunctive normal form Fórmula CNF Logique booléenne Boolean logic Lógica booleana Redondance Redundancy Redundancia Satisfaction contrainte Constraint satisfaction Satisfaccion restricción Satisfiabilité Satisfiability Satisfactibilidad
Sonstiges:	Nachgewiesen in: PASCAL Archive Sprachen: English Original Material: INIST-CNRS Document Type: Conference Paper File Description: text Language: English Author Affiliations: Microsoft Research Silicon Valley Lab, 1065 La Avenida Ave, Sunnyvale, CA 94043, United States Rights: Copyright 2005 INIST-CNRS ; CC BY 4.0 ; Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS Notes: Computer science; theoretical automation; systems

Klicken Sie ein Format an und speichern Sie dann die Daten oder geben Sie eine Empfänger-Adresse ein und lassen Sie sich per Email zusenden.

BibTeX Citavi, JabRef, u.a.
(Literaturverwaltung)

PDF kein Volltext!
(Merkzettel, Notizen)

RIS Endnote, Citavi u.a.
(Literaturverwaltung)

MODS
(XML zur Weiterverarbeitung)

oder

Wählen Sie das für Sie passende Zitationsformat und kopieren Sie es dann in die Zwischenablage, lassen es sich per Mail zusenden oder speichern es als PDF-Datei.

Gewünschter Zitations-Stil:

oder

Bitte prüfen Sie, ob die Zitation formal korrekt ist, bevor Sie sie in einer Arbeit verwenden. Benutzen Sie gegebenenfalls den "Exportieren"-Dialog, wenn Sie ein Literaturverwaltungsprogramm verwenden und die Zitat-Angaben selbst formatieren wollen.