Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2006-04-19
2009-10-27
Chiang, Jack (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
07610570
ABSTRACT:
An improved method and mechanism for designing and verifying an electrical circuit design is provided using an improved SAT-solver which uses complete assignments and systematic local search to provides improved performance. In one approach, the sat-solver maintains a complete assignment that is changed one variable at a time. A variable is fixed within the falsified set of clauses.
REFERENCES:
patent: 6247164 (2001-06-01), Ashar et al.
J. Hao, L. Tétart, “CH-SAT: A Complete Heuristic Procedure for Satisfiability Problems”, ECAI-96 Workshop on Advances in Propositional Deduction, Aug. 1996.
E. Goldberg, Y. Novikov, “Berkmin: A fast and robust SAT-solver”, Proceedings of the Design, Automation, and Test in Europe Conference and Exhibition, Mar. 2002, pp. 142-149.
Baptista, L. et al.; “The Interplay of Randomization and Learning of Real-World Instances of Satisfiability”; Proceedings of the AAAI Workshop on Leveraging Probability and Uncertainty in Computation; Jul. 2000.
Bayardo, R. et al.; “Using CSP Look-Back Techniques to Solve Real-World SAT Instances”; Proceedings of the Fourteenth National Conference on Artifical Intelligence and Ninth Innovative Applications of Artifical Intelligence Conference; 1997; pp. 203-208; American Association for Artifical Intelligence Press; USA.
Ben-Sasson, E. et al.; “Near-Optimal Separation of Treelike and General Resolution”; Electronic Colloquium on Computational Complexity, Report No. 5; Third Workshop on the Satisfiabiility Problem—May 2000; Jan. 17, 2000; pp. 14-18; ECCC; Israel.
Biere, A., et al.; “Symbolic Model Checking Using SAT Procedures Instead of BDDs”; Proceedings of Design Automation Conference—DAC'99; 1999; pp. 317-320; ACM; USA.
Brayton, R.K., et al.; “Logic Minimization Algorithms for VLSI Synthesis”; Kluwer Academic Publishers, 1984; USA.
Burch, J. R., et al.; “Tight Integration of Combination Verification Methods”; Proceedings of the International Conference on Computer-Aided Design; 1998; pp. 570-576; ACM, USA.
Davis, M., et al.; “A Machine Program for Theorem-Proving”; Communications of the ACM; 1962; pp. 394-397; USA.
Dubois, O., et al.; “SAT versus UNSAT”; Second DIMACS Series in Discrete Mathematics and Theoretical Computer Science; 1996; pp. 415-436; vol. 26; American Mathematical Society.
Freeman, J.W.; “Improvements to Propositional Satisfiability Search Algorithms”; A Dissertation in Computer and Information Science, University of Pennsylvania, 1995; 1995; USA.
Goldberg, E. et al.; “Using SAT for Combinational Equivalence Checking”; Proceedings of the Design Automation and Test in Europe Conference—2001; 2001; pp. 114-121; IEEE; USA.
Gomes, C. P., et al.; “Boosting Combinatorial Search Through Randomization”; Proceedings of the International Conference on Principles and Practice of Constraint Programming; 1998; pp. 431-437; American Association for Artificial Intelligence Press/ The MIT Press; USA.
Gomes; C. P., et al.; “Heavy-Tailed Distributions in Combinatorial Search”; Principles and Practice of Constraint Programming—CP97; 1997; pp. 121-135; Springer.
Li, C. M.; “A Constraint-Based Approach to Narrow Search Trees for Satisfiability”; Information Processing Letters 71; 1999; pp. 75-80; vol. 71; Elsevier Science B.V.; France.
Marques-Silva, J.; “The Impact of Branching Heuristics in Propositional Satisfiability Algorithms”; Proceedings of the 9th Portuguese Conference on Artificial Intelligence (EPIA); Sep. 1999; LNAI; pp. 62-74; 1695; Portugal.
Marques-Silva, J. P. et al.; “GRASP: A New Search Algorithm for Satisfiability”; CSE-TR-292-96; Apr. 10, 1996; pp. 1-17; The University of Michigan; USA.
Marques-Silva, J. P. et al.; “GRASP: A Search Algorithm for Propositional Satisfiability”; IEEE Transactions on Computers; May 1999; pp. 506-521; vol. 48; No. 5.
Moskewicz, M. W. et al.; “Chaff: Engineering an Efficient SAT Solver”; Proceedings of the 38th Design Automation Conference -DAC '01; 2001; pp. 530-535; ACM; USA.
Novikov, Y. A.; “Using Restarts When Solving SAT-Instances”; Proceedings of the Fourth International Conference on Computer-Aided Design of Discrete Devices CAD DD '01; 2001; pp. 166-174; vol. 3; National Academy of Sciences of Belarus Institute of Engineering Cybernetics; Republic of Belarus.
Stephan, P., et al.; “Combinational Test Generation Using Satisfiability”; IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems; Sep. 1996; pp. 1167-1176; vol. 15; No. 9; IEEE; USA.
Velev, M. N.; Curriculum Vitae; 2004; http://www.ece.cmu.edu/˜mvelev.
Zhang, H.; “SATO; An Efficient Propositional Prover”; Proceedings of the 14th International Conference on Automated Deduction—CADE- 14; Jul. 1997; pp. 272-275; Springer; Australia.
www.satlib.org/benchm.html; SATLIB—Benchmark Problems; 2004.
www.lri.fr/˜simon/satex/satex.php3; The SAT-Ex site; 2004.
Fang, H. et al.; “Complete Local Search for Propositional Satisfiability”; Proceedings of 19th National Conference on Artificial Intelligence; 2004; pp. 161-166.
Goldberg, E.; “Testing Satisfiability of CNF Formulas by Computing a Stable Set of Points”; Annals of Mathematics and Artificial Intelligence (2005) 43: 65-89; Springer 2004.
Selman, B. et al.; “Noise Strategies for Improving Local Search”; AAAI; 1994; pp. 337-343; Seattle.
Habet, D. et al.; “A Hybrid Approach for SAT”; International Conference on Principles and Practice of Constraint Porgramming; 2002; pp. 172-184.
Mazure, B. et al.; “Boosting Complete Techniques Thanks to Local Search Methods”; Annals of Math. and Artif. Intelligence; 1998; pp. 319-331; vol. 22.
Prestvvich, S.; “Local Search and Backtracking vs. Non-Systematic Backtracking”; AAAI Fall Symposium on Using Uncertainty Within Computation; Nov. 2-4, 2001; pp. 109-115; North Falmouth, Cape Cod, MA.
Cadence Design Systems Inc.
Chiang Jack
Lin Aric
Vista IP Law Group LLP.
LandOfFree
Method and mechanism for using systematic local search for... 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 mechanism for using systematic local search for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and mechanism for using systematic local search for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4082222