Document Detail

Solving satisfiability with less searching.
MedLine Citation:
PMID:  21869218     Owner:  NLM     Status:  In-Data-Review    
A new technique, complement searching, is given for reducing the amount of searching required to solve satisfiability (constraint satisfaction) problems. Search trees for these problems often contain subtrees that have approximately the same shape. When this occurs, knowledge that the first subtree does not have a solution can be used to reduce the searching in the second subtree. Only the part of the second subtree which is different from the first needs to be searched. The pure literal rule of the Davis-Putnam procedure is a special case of complement searching. The new technique greatly reduces the amount of searching required to solve conjunctive normal form predicates that contain almost pure literals (literals with a small number of occurrences).
P W Purdom
Related Documents :
2343418 - From informed consent to informed refusal.
22011118 - Client-therapist agreement on target problems, working alliance, and counseling outcome.
18583088 - Clinical geneticists' and genetic counselors' views on the communication of genetic ris...
16541508 - Medicare prescription nightmare: overview january 28, 2006.
11895238 - A schematic approach to diagnosing and resolving lecturalgia.
16315448 - Speech understanding in quiet and noise, with and without hearing aids.
Publication Detail:
Type:  Journal Article    
Journal Detail:
Title:  IEEE transactions on pattern analysis and machine intelligence     Volume:  6     ISSN:  0162-8828     ISO Abbreviation:  IEEE Trans Pattern Anal Mach Intell     Publication Date:  1984 Apr 
Date Detail:
Created Date:  2011-08-26     Completed Date:  -     Revised Date:  -    
Medline Journal Info:
Nlm Unique ID:  9885960     Medline TA:  IEEE Trans Pattern Anal Mach Intell     Country:  United States    
Other Details:
Languages:  eng     Pagination:  510-3     Citation Subset:  -    
Department of Computer Science, Indiana University, Bloomington, IN 47405.
Export Citation:
APA/MLA Format     Download EndNote     Download BibTex
MeSH Terms

From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine

Previous Document:  Word-meaning selection in multiprocess language understanding programs.
Next Document:  Matching three-dimensional objects using silhouettes.