Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2005-06-28
2005-06-28
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000, C716S030000, C703S016000, C706S013000, C706S016000, C706S033000, C706S045000
Reexamination Certificate
active
06912700
ABSTRACT:
A computerized method and system for solving non-linear Boolean equations is disclosed comprising at least partially solving a Boolean function; developing at least one inference regarding said Boolean function and saving said inference to a state machine; and accessing said inference from said state machine to develop at least one heuristic for determining whether said Boolean function is satisfiable.
REFERENCES:
patent: 4649515 (1987-03-01), Thompson et al.
patent: 4658370 (1987-04-01), Erman et al.
patent: 4713775 (1987-12-01), Scott et al.
patent: 5136686 (1992-08-01), Koza
patent: 5195172 (1993-03-01), Elad et al.
patent: 5265222 (1993-11-01), Nishiya et al.
patent: 5434952 (1995-07-01), Yen et al.
patent: 5636328 (1997-06-01), Kautz et al.
patent: 5649165 (1997-07-01), Jain et al.
patent: 5734798 (1998-03-01), Allred
patent: 6058385 (2000-05-01), Koza et al.
patent: 6308299 (2001-10-01), Burch et al.
patent: 6343376 (2002-01-01), Saxe et al.
patent: 6408262 (2002-06-01), Leerberg et al.
patent: 6496961 (2002-12-01), Gupta et al.
patent: 6560758 (2003-05-01), Jain
patent: 6640231 (2003-10-01), Andersen et al.
patent: 6681373 (2004-01-01), Zolotykh et al.
patent: 2001/0010091 (2001-07-01), Noy
patent: 2002/0178424 (2002-11-01), Gupta et al.
patent: 2004/0015799 (2004-01-01), Jain
Mukherjee et al., “VERIFUL: Verification Using Functional Learning”, European Design and Test Conference, Mar. 6, 1995, pp 444-448.
NN9105435, “State Machine Verification Expert”, IBM Technical Disclosure Bulletin, vol. 33, No. 12, May 1991, pp. 435-436 (4 pages).
Kunz et al., “Recursive Learning: A New Implication Technique for Efficient Solutions to CAD Problems—Test, Verification, and Optimization”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 13, No. 9, pp. 1143-115.
Li et al., “Programming model for concept learning and its solution based on genetic algorithms”, Proceedings of the 3rd World Congress on Intelligent Control and Automation, Jun. 28, 2000, vol. 1, pp. 299-303.
Kondo et al., “Design and heuristics for BDD-based automated termination verification system for rule-based programs”, IEEE SMC '99 Conference Proceedings, 1999 IEEE International Conference on Systems, Man and Cybernetics, vol. 5, Oct. 12, 1999, pp. 738.
Kurihara et al., “BDD encoding for partial order constraints and its application to expert systems in software verification domains”, 2000 IEEE International Conference on Systems, Man and Cybernetics, vol. 3, Oct. 8, 2000, pp. 2062-2067.
Holman, “A framework for determining the satisfiability of general Boolean expressions”, Proceedings of the 37th Midwest Symposium on Circuits and Systems, vol. 1, Aug. 3, 1994, pp. 381-384.
Chatalic, Philippe, et al., “Multi-Resolution on Compressed Sets of Clauses,” pp. 1-10, no date.
Baher, R. Iris et al., “Power Optimization of Technology-Dependent Circuits Based on Symbolic Computation of Logic Implications,” pp. 1-24, no date.
Paruthi, Viresh, et al., “Equivalence Checking Combining a Structural SAT-Solver, BDDs, and Simulation” (pp. 459-464), IEEE, 2000.
Wilson, Chris, et al., “Reliable Verification Using Symbolic Simulation with Scalar Values,” pp. 1-6, no date.
Kalla, Priyank, et al., “A BDD-Based Satisfiability Infrastructure Using the Unate Recursive Paradigm,” Technical Report: TR-CSE-99-6, pp. 1-10, no date.
Gupta, Aarti, et al., “Fast Error Diagnosis for Combinational Verification,” pp. 1-7, no date.
Prasad, Mukul R., et al., “Why is ATPG easy?”, pp. 1-7, no date.
Bryant, Randal E., et al., “Microprocessor Verification Using Efficient Decision Procedures for a Logic of Equality with Uninterpreted Functions,” Jun. 1999, pp. 1-13.
Biere, Armin, et al., “Symbolic Model Checking without BDDs”; Submitted for TACAS (1999), Jan. 4, 1999, pp. 1-17.
Tragoudas, S. et al., “Functional ATPG for Delay Faults,” pp. 1-4, no date.
Nam, Gi-Joon, et al., “Satisfiability-Based Layout Revisited: Detailed Routing of Complex FPGAs Via Search-Based Boolean SAT,” (pp. 167-175), ACM, 1999.
Bollig, et al, “Hierarchy Theorems for κOBDDs and κIBDDs,” pp. 1-18, no date.
Wood, R. Glenn, et al., “FPGA Routing and Routability of Estimation Via Boolean Satisfiability,” IEEE Transaction on VLSI Systems, vol. 6, No. 2, Jun. 1998, pp. 222-231.
Gupta, Aarti, et al., “Integrating a Boolean Satisfiability Checker and BDDs for Combinational Equivalence Checking,” (pp. 222 225), IEEE, 1997.
Cyrluk, David et al., “An Efficient Decision Procedure for the Theory of Fixed-Sized Bit-Vectors,” pp. 1-10, no date.
Takagi, Kazuyoshi, et al., “Computational Power of Nondeterministic Ordered Binary Decision Diagrams and Their Subclasses,” IEICE Trans. Fundamentals E80:4, pp. 663-669 (Apr. 1997).
Kawakubo, Kasuo, et al., “Formal Verification of Self-Testing Properties of Combinational Circuits,” Proceedings of ATS '96, pp. 119 122, IEEE, 1996.
Puri, Ruchir, et al., “A BDD SAT solver for satisfiability testing: An industrial case study,” Annals of Mathematics and Artificial Intelligence 17, pp. 315-337 (1996).
Groote, Jan F, “Hiding Propositional Constants in BDDs,” pp. 1-6, no date.
Nakaoka, Toshihiro, et al., “A Verification Algorithm for Logic Circuits with Internal Variables,” pp. 1920-1923, IEEE, 1995.
Ashar, Pranav, et al., “Boolean Satisfiability and Equivalence Checking Using General Binary Decision Diagrams,” pp. 259 264, no date.
Burch, J.R., et al., “Symbolic Model Checking: 1020States and Beyond,” pp. 1-33, no date.
Bryant, Randal E., et al., “Processor Verification Using Efficient Reductions of the Logic of Uninterpreted Functions to Propositional Logic,” May, 1999, Carnegie Mellon University, pp. 1-45.
Biere, A., et al., “Symbolic Model Checking using SAT procedures instead of BDDs,” pp. 1-4, no date.
Dransfield Michael R.
Franco John V.
Schlipf John
VanFleet W. Mark
Frost Brown Todd LLC
Kik Phallaka
Smith Matthew
The United States of America as represented by the National Secu
The University of Cincinnati
LandOfFree
Method and system for non-linear state based satisfiability 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 system for non-linear state based satisfiability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for non-linear state based satisfiability will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3488274