Document Detail


Solving satisfiability with less searching.
MedLine Citation:
PMID:  21869218     Owner:  NLM     Status:  In-Data-Review    
Abstract/OtherAbstract:
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).
Authors:
P W Purdom
Related Documents :
19000958 - Using the timing information of heartbeats as an entity identifier to secure body senso...
12284768 - The sample of anonymised records.
2796748 - The access of relevant information for solving problems.
12289238 - Decree relating to health education and information on youth as well as to aid and assi...
657648 - Rehabilitation of the communicatively impaired stroke patient.
3126898 - Survey of general practitioners' attitudes to aids in the north west thames and east an...
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:  -    
Affiliation:
Department of Computer Science, Indiana University, Bloomington, IN 47405.
Export Citation:
APA/MLA Format     Download EndNote     Download BibTex
MeSH Terms
Descriptor/Qualifier:

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.