Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2007-07-24
2007-07-24
Whitmore, Stacy A (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C703S002000
Reexamination Certificate
active
11038958
ABSTRACT:
Quantified Boolean formula (QBF) techniques are used in determining QBF satisfiability. A QBF is broken into component parts that are analyzable by a satisfiability (SAT) solver. Each component is then independently, and perhaps in parallel, analyzed for satisfiability. If a component is unsatisfiable, then it is determined that the QBF is unsatisfiable, and the analysis is stopped. If a component is satisfiable, then an assignment corresponding to the satisfiable component is noted. If a component is satisfiable, then it is appended to another untested component to provide a combination component, and the satisfiability of the combination component is analyzed. Such appending and analysis is repeated until the QBF is completed and determined to be satisfiable or determined to be unsatisfiable.
REFERENCES:
patent: 6131078 (2000-10-01), Plaisted
patent: 6321186 (2001-11-01), Yuan et al.
patent: 6442732 (2002-08-01), Abramovici et al.
patent: 7031896 (2006-04-01), Yang
patent: 7058910 (2006-06-01), Bharadwaj et al.
patent: 7107553 (2006-09-01), Lockyear et al.
patent: 7117463 (2006-10-01), Graham et al.
patent: 2003/0225552 (2003-12-01), Ganai et al.
Zhang, Lintao, et al., “The Quest for Efficient Boolean Satisfiability Solvers,” Proceedings of 8thInternational Conference on Computer Aided Deduction (CADE 2002) and also in Proceedings of 14thConference on Computer Aided Verification (CAV 2002), Copenhagen, Denmark, Jul. 2002, 20 pages.
Plaisted, David A., et al., “A Satisfiability Procedure for Quantified Boolean Formulae,” Preprint submitted to Discrete Applied Mathematics (Mar. 26, 2002), pp. 1-46.
Cadoli, Marco, et al., “An Algorithm to Evaluate Quantified Boolean Formulae,” Proceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI-98) and the Tenth Conference on Innovative Applications of Artificial Intelligence (IAAI-98), AAAI Press/The MIT Press, Jul. 1998, 6 pages.
Büning, Hans Kleine, et al., “Resolution for Quantified Boolean Formulas,” Information and Computation, v. 117, n. 1, Feb. 15, 1995, 3 pages.
http://www4.informatik.tu-meunchen.de/˜letz/semprop/, “SEMPROP—A Decision Procedure for Quantified Boolean Formulas,” 2002, 2 pages.
http://www.mrg.dist.unige.it/˜qube/barLeft.html, QuBE, Quantified Boolean formulas Evaluator, 2001, 2 pages.
http://www.princeton.edu/˜chaff/quaffle.html, “Quaffe, Quantified Boolean Formula Evaluator with Learning,” 2002, 1 page.
http://www.inf.ethz.ch/personal/biere/projects/quantor/, “QUANTOR QBF Solver,” Jan. 2004, 1 page.
http://sra.itc.it/people/benedetti/sKizzo/, “Welcome to the home page of sKizzo a QBF Solver,” Nov. 2004, 3 pages.
Flanagan, Cormac, et al., “An Explicating Theorem Prover for Quantified Formulas,” Intelligent Enterprise Technologies Laboratory, HP Laboratories Palo Alto, Nov. 2, 2004, 15 pages.
Yu Yuan
Zhang Lintao
Whitmore Stacy A
Woodcock & Washburn LLP
LandOfFree
Quantified boolean formula (QBF) 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 Quantified boolean formula (QBF) solver, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantified boolean formula (QBF) solver will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3748963