Data processing: structural design – modeling – simulation – and em – Simulating electronic device or electrical system
Reexamination Certificate
2006-04-18
2006-04-18
Broda, Samuel (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Simulating electronic device or electrical system
C703S022000, C703S002000, C716S030000
Reexamination Certificate
active
07031896
ABSTRACT:
Methods for formal verification of circuits and other finite-state systems are disclosed. Formal definitions and semantics are disclosed for a model of a finite-state system, an assertion graph to express properties for verification, and satisfiability criteria for specification and automated verification of forward implication properties and backward justification properties. A method is disclosed to perform antecedent strengthening on antecedent labels of an assertion graph.A method is also disclosed to compute a simulation relation sequence ending with a simulation relation fixpoint, which can be compared to a consequence labeling for each edge of an assertion graph to verify implication properties properties according to the formal semantics. An alternative method is disclosed to compute the simulation relation sequence from the strengthened antecedent labels of an assertion graph, thereby permitting automated formal verification of justification properties.Finally methods are disclosed to significantly reduce computation through abstraction of models and assertion graphs and to compute an implicit satisfiability of an assertion graph by a model from the simulation relation computed for the model and assertion graph abstractions. Other methods and techniques are also disclosed herein, which provide for fuller utilization of the claimed subject matter.
REFERENCES:
patent: 5119318 (1992-06-01), Paradies et al.
patent: 5469367 (1995-11-01), Puri et al.
patent: 5481717 (1996-01-01), Gaboury
patent: 5491639 (1996-02-01), Filkorn
patent: 5594656 (1997-01-01), Tamisier
patent: 5691925 (1997-11-01), Hardin et al.
patent: 5754454 (1998-05-01), Pixley et al.
patent: 5768498 (1998-06-01), Boigelot et al.
patent: 5870590 (1999-02-01), Kita et al.
patent: 5905977 (1999-05-01), Goubault
patent: 5937183 (1999-08-01), Ashar et al.
patent: 6026222 (2000-02-01), Gupta et al.
patent: 6035109 (2000-03-01), Ashar et al.
patent: 6086626 (2000-07-01), Jain et al.
patent: 6131078 (2000-10-01), Plaisted
patent: 6148436 (2000-11-01), Wohl
patent: 6185516 (2001-02-01), Hardin et al.
patent: 6209120 (2001-03-01), Kurshan et al.
patent: 6247165 (2001-06-01), Wohl et al.
patent: 6292916 (2001-09-01), Abramovici et al.
patent: 6301687 (2001-10-01), Jain et al.
patent: 6308299 (2001-10-01), Burch et al.
patent: 6321186 (2001-11-01), Yuan et al.
patent: 6339837 (2002-01-01), Li
patent: 6341367 (2002-01-01), Downing
patent: 6484134 (2002-11-01), Hoskote
Sipma et al, “Deductive Model Checking,” Formal Methods in System Design, vol. 15, pp. 49-74 (1999) (text available at http://www-step.stanford.edu/papers/fmsd99.pdf).
Aagaard et al, “Formal Verification Using Parametric Representation of Boolean Constraints,” Proceedings of the 36th ACM/IEEE Conference on Design Automation, pp. 402-407 (Jun. 1999).
Aagaard et al, “Combining Theorem Proving and Trajectory Evaluation in an Industrial Environment,” Proceedings of the Design Automation Conference, pp. 538-541 (Jun. 1998).
Berezin, S. et al, “A Compositional Proof System for the Modal μ-Calculus and CCS,”Technical Report CMU-CS-97-105, Carnegie Mellon University, Jan. 15, 1997.
Berezin, S. et al, “Model Checking Algorithms for the μ-Calculus,”Technical Report CMU-CS-96-180, Carnegie Mellon University, Sep. 23, 1996.
Bryant, R. E. et al, “Formal Hardware Verification by Symbolic Ternary Trajectory Evaluation,”28thACM/IEEE Design Automation Conference, Paper 24.2, 1991, pp. 397-402.
Bryant, R. E., “Binary Decision Diagrams & Beyond,” Tutorial at ICCAD '95,Carnegie Mellon University, 1995.
Burch, J. R. et al, “Representing Circuits More Efficiently in Symbolic Model Checking,”28thACM/IEEE Design Automation Conference, Paper 24.3, 1991, pp. 403-407.
Burch, J. R. et al, “Sequential Circuit Verification Using Symbolic Model Checking,”27thACM/IEEE Design Automation Conference, Paper 3.2, 1990, pp. 46-51.
Campos, S., “Real-Time Symbolic Model Checking for Discrete Time Models,”Technical Report CMU-CS-94-146, Carnegie Mellon University, Pittsburgh, PA, May 2, 1994.
Chan, W. et al, Combining Constraint Solving and Symbolic Model Checking for a Class of Systems with Non-linear Constraints,Computer Aided Verification, 9thInternational Conference, CAV '97 Proceedings(O. Grumberg, Editor), Lecture Notes in Computer Science 1254, pp. 316-327, Haifa, Israel, Jun. 1997. Springer-Verlag (Revised in Dec. '98).
Chen, Y. et al, “PBHD: An Efficient Graph Representation for Floating Point Circuit Verification,”Technical Report CMU-CS-97-134, Carnegie Mellon University, May 1997.
Cheung, S. et al, “Checking Safety Properties Using Compositional Reachability : Analysis,”ACM Transactions on Software Engineering and Methodology, vol. 8, No. 1, Jan. 1999, pp. 49-78.
Chiodo, M. et al, “Automatic Compositional Minimization in CTL Model Checking,”Proceedings of 1992 IEEE/ACM International Conference on Computer-Aided Design, Nov., 1992, pp. 172-178.
Chou, C., “The Mathematical Foundation of Symbolic Trajectory Evaluation,”International Conference on Computer-Aided Verification(CAV'99), Trento, Italy, Jul. 1999 pp. 196-207, Proceedings of CAV'99, Lecture Notes in Computer Science #1633 (Editors: Nicolas Halbwachs & Doron Peled), Springer-Verlog, 1999.
Clarke, E. et al, “Another Look at LTL Model Checking,”Technical Report CMU-CS-94-114, Carnegie Mellon University, Feb. 23, 1994.
Clarke, E. et al, “Combining Symbolic Computation and Theorem Proving: Some Problems of Ramanujan,”Technical Report CMU-CS-94-103, Carnegie Mellon University, Jan. 1994.
Clarke, E. M. et al, “Formal Methods: State of the Art and Future Directions,”ACM Computing Surveys, vol. 28, No. 4, Dec. 1996, pp. 626-643.
Clarke, E. M. et al, “Model Checking and Abstraction,”Proceedings of the 19thACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Feb. 1992, pp. 343-354.
Clarke, E. M. et al, “Model Checking and Abstraction,”ACM Transactions on Programming Languages and Systems, vol. 16, No. 5, Sep. 1994, pp. 1512-1542.
Grumberg, O., “Model Checking and Modular Verification,”ACM Transactions On Programming Languages and Systems, vol. 16, No. 3, May 1994, pp. 843-871.
Jackson, D., “Exploiting Symmetry in the Model Checking of Relational Specifications,”Technical Report CMU-CS 94-219, Carnegie Mellon University, Dec. 1994.
Jain, A. et al, “Verifying Nondeterministic Implementations of Determinist Systems,”Lecture Notes in Computer Science, Formal Methods in Computer Aided-Design, pp. 109-125, Nov. 1996.
Jain, A., “Formal Hardware Verification by Symbolic Trajectory Evaluation,”Carnegie Mellon University Ph.D. Dissertation, Jul. 1997.
Jain, S. et al, “Automatic Clock Abstraction from Sequential Circuits,”Proceedings of the 32ndACM/IEEE Conference on Design Automation, Jan. 1995.
Jha, S. et al, “Equivalence Checking Using Abstract BBDs,”Technical Report CMU-CS-96-187, Carnegie Mellon University, Pittsburgh, PA, Oct. 29, 1996.
Kern, C. et al, “Formal Verification In Hardware Design: A Survey,”ACM Transactions on Design Automation of Electronic Systems, vol. 4, No. 2, Apr. 1999, pp. 123-193.
Kurshan, R. et al, “Verifying Hardware in its Software Context,”Proceedings of the 19thACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Feb. 1992, pp. 742-749.
Nelson, K. L. et al, “Formal Verification of a Superscalar Execution Unit,”34thDesign Automation Conference, Jun. 1997.
Tuya, J. et al, “Using a Symbolic Model Checker for Verify Safety Properties in SA/RT Models,”Proceeding of the 5h European Software Engineering Conference, Lecture Notes in Computer Science, vol. 989, Springer-Verlag, Berlin, 1995, pp. 59-75.
Velev, M. N., “Efficient Modeling of Memory Arrays in Symbolic Simul
Broda Samuel
Intel Corporation
Mennemeier Larry M.
LandOfFree
Methods for performing generalized trajectory evaluation 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 for performing generalized trajectory evaluation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods for performing generalized trajectory evaluation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3607880