Data processing: structural design – modeling – simulation – and em – Modeling by mathematical expression
Reexamination Certificate
2002-09-09
2008-08-26
Rodriguez, Paul (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Modeling by mathematical expression
C703S014000
Reexamination Certificate
active
07418369
ABSTRACT:
Disclosed is a complete SAT solver, Chaff, which is one to two orders of magnitude faster than existing SAT solvers. Using the Davis-Putnam (DP) backtrack search strategy, Chaff employs efficient Boolean Constraint Propagation (BCP), termed two literal watching, and a low overhead decision making strategy, termed Variable State Independent Decaying Sum (VSIDS). During BCP, Chaff watches two literals not assigned to zero. The literals can be specifically ordered or randomly selected. VSIDS ranks variables, the highest-ranking literal having the highest counter value, where counter value is incremented by one for each occurrence of a literal in a clause. Periodically, the counters are divided by a constant to favor literals included in recently created conflict clauses. VSIDS can also be used to select watched literals, the literal least likely to be set (i.e., lowest VSIDS rank, or lowest VSIDS rank combined with last decision level) being selected to watch.
REFERENCES:
patent: 6038392 (2000-03-01), Ashar
patent: 6247164 (2001-06-01), Ashar
patent: 6651234 (2003-11-01), Gupta
Matthew W. Moskewicz, Conor F. Madigan, Ying Zhao, Lintao Zhang, Sharad Malik; “Chaff: Engineering an Efficient SAT Solver”; Jun. 18-22, 2001; DAC 2001; pp. 530-535.
Udi Manber, “Introduction to Algorithms, A Creative Approach”, 1989, Addison-Wesley Publishing Company, Inc., pp. 344-347, 356-363.
Peixin Zhong, Pranav Ashar, Sharad Malik, Margaret Martonosi; “Using Reconfigurable Computing Techniques to Accelerate Problems in the CAD Domain: A Case Study with Boolean Satisfiability”; Jun. 15-19, 1998; DAC 1998; pp. 194-199.
Joäo P. Marques-Silva and Karem A. Sakallah, “Boolean Satisfiability in Electronic Design Automation”, 2000, ACM, p. 675-680.
Mark Overmars, “Programming Lego Robots using NQC”, Oct. 2, 1999, Utrecht University, pp. 1-43.
Marques-Silva, J. P., and Sakallah, K. A., “GRASP: A Search Algorithm for Propositional Satisfiability,” IEEE Transactions on Computers, 1063-6757/96, 220-227, 1996, 7 pages.
Zhang, H., “SATO: An Efficient Propositional Prover,” Proceedings of the International Conference on Automated Deduction, pp. 272-275, Jul. 1997, 4 pages.
M. Davis and H. Putnam, A Computing Procedure for Quantification Theory, Journal of the ACM, 7:201-215, 1960, 15 pages.
M. Davis, G. Logemann and D. Loveland, “A Machine Program for Theorem-Proving”, Communications of the ACM, vol. 5, No. 7, pp. 394-397, 1962, 4 pages.
Marques-Silva, J. P., The Impact of Branching Heuristics in Propositional Satisfiability Algorithms, Proceedings of the 9th Portuguese Conference on Artificial Intelligence (EPIA), Sep. 1999, 13 pages.
R. Bayardo, and R. Schrag, “Using CSP Look-Back Techniques to Solve Real-World SAT Instances”, Proceedings of the 14th Nat. (US) Conf. on Artificial Intelligence (AAAI-97), AAAI Press/The MIT Press, 203-208, 1997, 6 pages.
L. Zhang, C. Madigan, M. Moskewicz and S. Malik, “Efficient Conflict Driven Learning in a Boolean Satisfiability Solver,” Proceedings of the International Conference on Computer-Aided Design (ICCAD), 2001, 7 pages.
L. Baptista, I. Lynce and J. Marques-Silva, “Complete Search Restart Strategies for Satisfiability,” IJCAI '01 Workshop on Stochastic Search Algorithms (IJCAI-SSA), Aug. 2001, 5 pages.
Madigan Conor
Malik Sharad
Moskewicz Matthew
Dann Dorfman Herrell and Skillman
Haun Niels
Proctor Jason
Rodriguez Paul
The Trustees of Princeton University
LandOfFree
Method and system for efficient implementation of boolean... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for efficient implementation of boolean..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for efficient implementation of boolean... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4002793