Scheduling events in a boolean satisfiability (SAT) solver

Details Scheduling events in a boolean satisfiability (SAT) solver Scheduling events in a boolean satisfiability (SAT) solver

2007-03-20

2007-03-20

Lin, Sun James (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000

Reexamination Certificate

active

10807959

ABSTRACT:
In one embodiment, a method for scheduling events in a Boolean satisfiability (SAT) solver includes collecting one or more first-order statistics on a search for a valid solution to an SAT problem, deriving one or more second-order statistics on the search from the one or more first-order statistics, and scheduling events in the search according to one or more of the second-order statistics.

REFERENCES:
patent: 6556978 (2003-04-01), Ginsberg et al.
patent: 6651234 (2003-11-01), Gupta et al.
patent: 6912700 (2005-06-01), Franco et al.
patent: 2003/0084411 (2003-05-01), Moskewicz et al.
patent: 2003/0225552 (2003-12-01), Ganai et al.
“Chaff: Engineering an Efficienct SAT Solver”, Proc. of the 38th Design Automation Conference, Jun. 2001, Moskewicz et al.
“The Quest for Efficeint Boolean Satisfiability Solvers”, Princeton University, 2002, Zhang et al.
“GRASP: A Search Algorithm for Porpositional Satisfiability”, IEEE Trans. on Computers, vol. 48, No. 5, May 1999, Marques-Silva et al.
Marques-Silva et al., “GRASP: A Search Algorithm for Propositional Satisfiability,” IEEE Trans. on Computers, vol. 48, No. 5, pp. 506-521, May 1999.
Moskewicz et al., “Chaff: Engineering and Efficient SAT Solver,” in Proc. of the 38th Design Automation Conference, Jun. 2001, pp. 530-535.
Zhang et al., “SATO: An Efficient Propositional Prover,” in Proc. of the International Conference on Automated Deduction, Jul. 1997, pp. 272-275.
Goldberg et al., “BerkMin: a Fast and Robust Sat-Solver,” in Proc. of Design and Test in Europe, Mar. 2002, pp. 142-149.
Stephen et al., “Combinational Test Generation Using Satisfiability,” IEEE Trans. in CAD, vol. 15, No. 9, pp. 1167-1176, Sep. 1996.
Biere et al., “Symbolic Model Checking without BDDs,” in Proc. of TACAS'99, Mar. 1999, pp. 193-207.
Bryant, et al., “Processor Verification Using Efficient Reductions of the Logic of Uninterpreted Functions to Propositional Logic,” ACM Trans. on Computational and Sequential Logic, vol. 2. No. 1, pp. 1-41, Jan. 2001.
Entrena et al., “Combinational and Sequential Logic Optimization by Redundancy Addition and Removal,” IEEE Trans. on CAD, vol. 14, No. 7, pp. 909-916, Jul. 1995.
Wood et al., “FPGA Routing and Routability Estimation via Boolean Satisfiability,” IEEE Trans. on VLSI, vol. 6, No. 2, pp. 222-231, Jun. 1998.
Davis et al., “A Machine Program for Theorem-Proving,” Communications of the ACM, vol. 5, pp. 394-397, Jul. 1962.

Affiliated with

Also associated with

Rating

Scheduling events in a boolean satisfiability (SAT) solver does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Scheduling events in a boolean satisfiability (SAT) solver, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheduling events in a boolean satisfiability (SAT) solver will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3766398