Data processing: structural design – modeling – simulation – and em – Simulating electronic device or electrical system – Event-driven
Reexamination Certificate
2007-10-16
2007-10-16
Ferris, Fred (Department: 2128)
Data processing: structural design, modeling, simulation, and em
Simulating electronic device or electrical system
Event-driven
C703S014000, C703S022000
Reexamination Certificate
active
09956571
ABSTRACT:
A state-transition system is extracted from a high-level description of a design. Assumptions regarding states of the design are determined for an initial clock cycle. Linear arithmetic relations are introduced to these assumptions. Guarantees are determine that provide properties of the design that hold after a fixed number of clock cycles. Symbolic simulation is performed for a limited number of clock cycles on the state transition system of the design. If the guarantees hold once simulation is performed, the design is verified. Otherwise, counter-examples are generated.
REFERENCES:
patent: 5163016 (1992-11-01), Har'El et al.
patent: 5502661 (1996-03-01), Glunz
patent: 5537580 (1996-07-01), Giomi et al.
patent: 5555201 (1996-09-01), Dangelo et al.
patent: 5680332 (1997-10-01), Raimi et al.
patent: 5774370 (1998-06-01), Giomi
patent: 5841663 (1998-11-01), Sharma et al.
patent: 5999717 (1999-12-01), Kaufmann et al.
patent: 6044211 (2000-03-01), Jain
patent: 6064819 (2000-05-01), Franssen et al.
patent: 6141790 (2000-10-01), Beausang et al.
patent: 6157901 (2000-12-01), Howe
patent: 6175946 (2001-01-01), Ly et al.
patent: 6378112 (2002-04-01), Martin et al.
patent: 6484134 (2002-11-01), Hoskote
patent: 6539345 (2003-03-01), Jones et al.
patent: 6591400 (2003-07-01), Yang
patent: 6654715 (2003-11-01), Iwashita
patent: 6728665 (2004-04-01), Gupta et al.
patent: 6848088 (2005-01-01), Levitt et al.
patent: 6944838 (2005-09-01), McMillan
patent: 6975976 (2005-12-01), Casavant et al.
patent: 2002/0046393 (2002-04-01), Leino et al.
patent: 2002/0099982 (2002-07-01), Andersen et al.
patent: 2003/0066039 (2003-04-01), Zhong et al.
patent: 2003/0225552 (2003-12-01), Ganai et al.
patent: 2004/0006451 (2004-01-01), Bharadwaj et al.
patent: 2004/0107174 (2004-06-01), Jones et al.
Extraction of finite state machines from transistor netlists by symbolic simulation Pandey, M.; Jain, A.; Bryant R.E.; Beatty, D.; York, G.; Jain, S.; Computer Design: VLSI in Computers and Processors, Oct. 2-4 1995. ICCD '95. Proceedings.pp. 596-601.
Formal verification based on assume and guarantee approach: a case study; Roy, S.K.; Iwashita, H.; Nakata, T.; Design Automation Conference, 2000. Proceedings of the ASP-DAC 2000. Asia and South Pacific , Jan. 25-28, 2000; pp. 77-80□□.
Equivalent design representations and transformations for interactive scheduling; Ang, R.P.; Dutt, N.D.; Computer-Aided Deign, 1992. ICCAD-92. Digest of Technical Papers., 1992 IEEE/ACM International Conference on , Nov. 8-12, 1992; pp. 332-335.
CTL model checking based on forward state traversal; Iwashita, H.; Nakata, T.; Hirose, F.;□□Computer-Aided Design, 1996. ICCAD-96. Digest of Technical Papers., 1996 IEEE/ACM International Conference on , Nov. 10-14, 1996; pp. 82-87□□.
A new model for improving symbolic product machine traversal;Cabodi, G.; Camurati, P.; Corno, F.; Gai, S.; Prinetto, P.; Sonza Reorda, M.;Design Automation Conference, 1992. Proceedings., 29th ACM/IEEE , Jun. 8-12, 1992; pp. 614-619.
On the complexity of modular model checking□□Vardi, M.Y.; Logic in Computer Science, 1995. LICS '95. Proceedings., Tenth Annual IEEE Symposium on , Jun. 26-29, 1995 ; pp. 101-111.
Symbolic simulation-techniques and applications; Bryant, R.E.; Design Automation Conference, 1990. Proceedings. 27th ACM/IEEE , Jun. 24-28, 1990; pp. 517-521.
Efficient generation of counterexamples and witnesses in symbolic model checking; E. M. Clarke, O. Grumberg, K. L. McMillan, X. Zhao; Jan. 1995 Proceedings of the 32nd ACM/IEEE conference on Design automation; Google & IEEE searches “dual next-state”.
Extraction of finite state machines from transistor netlists by symbolic simulation Pandey, M.; Jain, A.; Bryant, R.E.; Beatty, D.; York, G.; Jain, S.; Computer Design: VLSI in Computers and Processors, Oct. 2-4, 1995. ICCD '95. Proceedings.pp. 596-601.
On the complexity of modular model checking□□Vardi, M.Y.;Logic in Computer Science, 1995. LICS '95. Proceedings., Tenth Annual IEEE Symposium on , Jun. 26-29, 1995 ; pp. 101-111.
CTL model checking based on forward state traversal; Iwashita, H.; Nakata, T.; Hirose, F.;□□Computer-Aided Design, 1996. ICCAD-96. Digest of Technical Papers., 1996 IEEE/ACM International Conference on , Nov. 10-14, 1996; pp. 82-87.
Efficient generation of counterexamples and witnesses in symbolic model checking; E. M. Clarke, O. Grumberg, K. L. McMillan, X. Zhao; Jan. 1995 Proceedings of the 32nd ACM/IEEE conference on Design automation; Google & IEEE searches “dual next-state”.
Equivalent design representations and transformations for interactive scheduling; Ang, R.P.; Dutt, N.D.; Computer-Aided Design, 1992. ICCAD-92. Digest of Technical Papers., 1992 IEEE/ACM International Conference on , Nov. 8-12, 1992; pp. 332-335.
An introduction to assertional reasoning for concurrent system;A. Udaya Shankar; ACM Computing Surveys (CSUR);vol. 25 , Issue 3 (Sep. 1993); pp. 225-262 ISSN:0360-0300.
IEEE 1998 paper “Extending Statecharts with Temporal Logic” by Arcot Sowmya, Member, IEEE, and S. Ramesh.
Research paper “On the Construction of Automata from Linear Arithmetic Constraints” (2000) by Pierre Wolper, Bernard Boigelot.
M. Abadi and L. Lamport,Conjoining Specifications, ACM Trans. Prog. Lang. Syst., 17(3):507-533, May 1995.
R. Alur et al.,Automatic Symbolic Verification of Embedded Systems, Proc. of Real Time Systems Symposium, (37 pgs) 1993.
R. Alur et al.,Modularity for Timed and Hybrid Systems, Proceedings of the 8th International Conference on Concurrency Theory, (15 pgs) 1997.
R. Alur et al.,Partial-Order Reduction in Symbolic State Space Exploration, Proceedings of the 9th International Conference on Computer-aided Verification, (12 pgs) 1997.
R. Alur et al.,Reactive Modules, Proceedings of the 11thAnnual Symposium on Logic in Computer Science, (39 pgs) 1996.
R. Beckmann et al.,Application of Constraint Logic Programming for VLSI CAD Tools, Proc. 1stInt. Conf. Constraints in Computer Logic, (18 pgs) Sep. 1994.
S. Bensalem et al.,Powerful Techniques for the Automatic Generation of Invariants, Conference on Computer Aided Verification, (13 pgs) Jul. 1996.
A. Browne et al.,An Improved Algorithm for the Evaluation of Fixpoint Expressions, Sixth Conference on Computer Aided Verification, (27 pgs) 1994.
J.R. Burch,, et al.,Symbolic Model Checking: 1020States and Beyond, In Proc. of the 5thAnnual IEEE Symposium on Logic in Computer Science, pp. 428-439, (33 pages) 1990.
D. Currie et al.,Automatic Formal Verification of DSP Software, 37thDesign Automation Conference, (6 pgs) Jun. 2000.
D. Cyrluk, et al.,Effective Theorem Proving for Hardware Verification, Proceedings of the 2ndInternational Conference on Theorem Provers in Circuit Design, Theory, Practice, and Experience, vol. 901, pp. 203-222, 1994.
S. Das et al.,Experience With Predicate Abstraction, 11thInternational Conference on Computer-Aided Verification, (12 pgs) Jul. 1999.
M. Dwyer et al.,Filter-Based Model Checking of Partial Systems, Proceedings of the Sixth ACM SIGSOFT Symposium on Foundations of Software Engineering, (14 pgs) Nov. 1998.
S. Graf, et al.,Verifying Invariants Using Theorem Proving, Proceedings of the Eighth International Conference on Computer Aided Verification, vol. 1102, pp. 196-207, 1996.
E. P. Gribomont et al.,Simplification of Boolean Verification Conditions, Theoretical Computer Science, (25 pgs) 1999.
K. Havelund et al.,Experiments in Theorem Proving and Model Checking for Protocol Verification, Third International Symposium of Formal Methods Europe, (20 pgs) 1996.
T. A. Henzinger, et al.,You Assume, We Guarantee: Methodology and Case Studies, in Proc. of the 10thIntl. Conf. on Computer-Aided Verification, Vancouver, Canada (17 pgs) Jul. 1998.
W. Hunt et al.,The Verification of a Bit-slice ALU, Workshop on Hardware Specification, Verification and Synthesis: Mathematical Aspects, (28 pgs) 1989.
R. B. Jones, et al.,Efficient Validity Checking for Processor Verification, In Proc. IEEE Int. Conf. on Comput.-A
Christie Parker & Hale LLP
Ferris Fred
Fujitsu Limited
Saxena Akash
LandOfFree
High level verification of software and hardware... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High level verification of software and hardware..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High level verification of software and hardware... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3836468