Computer-aided design and analysis of circuits and semiconductor – Integrated circuit design processing – Logic design processing
Reexamination Certificate
2011-08-02
2011-08-02
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Integrated circuit design processing
Logic design processing
C716S107000
Reexamination Certificate
active
07992113
ABSTRACT:
An apparatus and methods for the production of satisfiability reports are provided. In an exemplary embodiment, a method of producing a report is provided. The method includes generating a complete assignment for a CNF formula, deriving first second sets of clauses that are unsatisfied by the reference point, making decision assignments, performing BCP then recomputing the second set of clauses. One feature of this embodiment is that it provides for efficient solutions for SAT problems. Other embodiments provide apparatus and software products that implement the disclosed methods. This Abstract is provided for the sole purpose of complying with the Abstract requirement rules that allow a reader to quickly ascertain the subject matter of the disclosure contained herein. This Abstract is submitted with the explicit understanding that it will not be used to interpret or to limit the scope or the meaning of the claims.
REFERENCES:
patent: 7356519 (2008-04-01), Goldberg et al.
patent: 2007/0299648 (2007-12-01), Levitt et al.
Biere, A.Cimatti, E.Clarke, O.Strichman, Y.Zhu. “Bounded Model Checking”, Advances in computers vol. 58, ed. by M. Zelkovitz, Elsevier, 2003.
Een et al, “An extensible SAT-solver”, Proceedings of SAT-2003 in LNCS 2919, pp. 503-518.
Fang et al, “Complete Local Search for Propositional Satisfiability”, Proc. of 19th National Conference on Artificial Intelligence, 2004, pp. 161-166.
Gelder, “Autarky pruning in propositional model elimination reduces failure redundancy”, J. of Autom. Reasoning,1999, vol. 23(2),pp. 137-193.
Goldberg, “Determinization of resolution by an algorithm operating on complete assignments”, SAT-2006, LNCS 4121, pp. 90-95.
Goldberg et al, “BerkMin: a Fast and Robust SAT-Solver”, Date-2002, Paris, pp. 142-149.
Gomes et al, “Boosting Combinatorial Search Through Randomization”, Proc. AAAI-98.
Habet et al, “A hybrid approach for SAT”, Int. Conf. on Principles and Practice of Constraint Programming, 2002, pp. 172-184.
Hirsch et al, “UnitWalk: A new SAT solver that uses local search guided by unit clause elimination”,Annals of Math. and Artif. Intell. 43(1-4), pp. 91-111, 2005.
Katz et al, “Space-efficient Bounded Model Checking”, Date-2005, pp. 686-687.
Kullmann, “Investigations on autark assignments”, Discrete Applied Mathematics 2000, vol. 107, pp. 99-137.
Li, “A constrained-based approach to narrow search trees for satisfiability”, Information processing letters, 1999, 71, pp. 75-80.
Moskewicz et al, “Chaff: Engineering an Efficient SAT Solver”, DAC-2001.
Prasad et al, “A survey of recent advances in SAT-based formal verification”, STTT vol. 7(2), pp. 16-173, 2005.
Prestwich, “Local search and backtracking vs. non-systematic backtracking”, AAAI Fall Symposium on Using Uncertainty Within Computation. Nov. 2-4, 2001, North Falmouth, Cape Cod, MA,pp. 109-115.
Selman et al, “A New Method for Solving Hard Satisfiability Problems”, AAAI-92, pp. 440-446.
Selman et al, “Noise strategies for improving local search”, AAAI-94, Seattle, pp. 337-343, 1994.
Silva et al, “GRASP: A Search Algorithm for Propositional Satisfiability”, IEEE Transactions of Computers, 1999, vol. 48, pp. 506-521.
Zhang et al, “Efficient Conflict Driven Learning in a Boolean Satisfiability Solver”, ICCAD-2001.
Zhang, “SATO: An efficient propositional prover”, International Conference on Automated Deduction, Jul. 1997, pp. 272-275.
Cadence Design Systems Inc.
Kilpatrick Townsend & Stockton LLP
Siek Vuthe
LandOfFree
Methods and apparatus for decision making in resolution... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for decision making in resolution..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for decision making in resolution... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2713761