Adaptive application of SAT solving techniques

Details Adaptive application of SAT solving techniques Adaptive application of SAT solving techniques

2005-07-11

2008-07-15

Chiang, Jack (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000

Reexamination Certificate

active

07401305

ABSTRACT:
A computer-implemented method for solving a satisfiability (SAT) problem includes defining a formula, including variables, which refers to properties of a target system. Using a chosen search strategy, a search process is performed over possible value assignments of the variables for a satisfying assignment that satisfies the formula. A performance metric estimating an effectiveness of the search process is periodically evaluated during the search process. The strategy of the search process is modified responsively to the evaluated performance metric. The method determines, using the search process, whether the formula is satisfiable on the target system.

REFERENCES:
patent: 6496961 (2002-12-01), Gupta et al.
patent: 6651234 (2003-11-01), Gupta et al.
patent: 6728939 (2004-04-01), Johannsen
patent: 6944838 (2005-09-01), McMillan
patent: 7028279 (2006-04-01), Jain et al.
patent: 7047139 (2006-05-01), Shtrichman
patent: 7203917 (2007-04-01), Ganai et al.
patent: 2002/0123867 (2002-09-01), Shtrichman
patent: 2006/0031730 (2006-02-01), Hsiao et al.
Bryant, “Graph-based Algorithms for Boolean Function Manipulation,” IEEE Transactions on Computers, (35:8), Aug. 1986, pp. 677-691.
Biere et al. , “Symbolic Model Checking Without BDDs,” Tools and Algorithms for the Construction and Analysis of Systems Fifth International Conference (TACAS'99) vol. 1579 of Lecture Notes in Computer Science, Jul. 1999, pp. 193-207.
Davis et al., “A machine program for theorem-proving,” Communications of the ACM, (5:7), pp. 394-397, Jul. 1962.
Merques-Silva and Sakallah, “Grasp: A Search Algorithm for Propositional Satisfiability,” IEEE Transactions on Computers, (48:5), May 1999, pp. 506-521.
Moskewicz et al., “Chaff: Engineering and Efficient SAT Solver,” Proceedings of the 38thAnnual IEEE/ACM Design Automation Conference (DAC'2001), Las Vegas, Nevada, Jun. 2001.
Goldberg and Novikov, “BerkMin: A Fast and Robust SAT Solver,” Proceedings of the Design Automation and Test in Europe (Date'2002) Conference, Paris, France, Mar. 2002, pp. 142-149.
Zhang, “SATO: An Efficient Propositional Prover,” Proceedings of the 14th International Conference on Automated Deduction, Townsville, Australia, Jul. 1997, pp. 272-275.
Nudelman et al., “SATzilla: An Algorithm Portfolio for SAT,” SAT 2003 Competition, in conjunction with the Sixth International Conference on the Theory and Applications of Satisfiability Testing.
Ryan, “Efficient Algorithms for Clause-Learning SAT Solvers,” M.Sc. Thesis, Simon Fraser University, Burnaby BC, Canada, Feb. 2004.
Lagoudakis and Littman, “Learning to Select Branching Rules in the DPLL Procedure for Satisfiability,” Electronic Notes in Discrete Mathematics (ENDM), vol. 9, LICS 2001 Workshop on Theory and Applications of Satisfiability Testing (SAT 2001), Boston.
Bayardo and Schrag, “Using CSP Loop-Back Techniques to Solve Real-World SAT Instances,” Proceedings of the 14th National Conference on Artificial Intelligence, Providence, Rhode Island, Jul. 1997, pp. 203-208.
Herbstritt and Becker, “Conflict-Based Selection of Branching Rules,” Proceedings of the Sixth International Conference on Theory and Application in Satisfiability Testing (SAT'2003), Santa Margherita Ligure, Italy, May 2003, pp. 441-451.
Aloul et al., “Satometer: How Much Have We Searched?” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, (22:8), Aug. 2003, pp. 995-1004.
Rule-Base parallel edition (RuleBase PE) formal verification tool produced by IBM Corporation (Armonk, New York), details at, www.haifa.il.ibm.com/projects/verification/RB—Homepage, printed Jan. 21, 2008.
McMillan, “Interpolation and SAT-based Model Checking,” Proceedings of the Fifteenth Conference on Computer-Aided Verification (CAV'03), Boulder, Colorado, Jul. 2003, (in vol. 2725 of Lecture Notes in Computer Science, Somenzi and Hunt, eds., pp. 1-13).

Affiliated with

Also associated with

Rating

Adaptive application of SAT solving techniques does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Adaptive application of SAT solving techniques, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive application of SAT solving techniques will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3966363