Formal Methods in Computer-Aided Design

1. Front Matter

   Pages I-XI

   PDF

2. Applications of Hierarchical Verification in Model Checking

   1. Applications of Hierarchical Verification in Model Checking

      • Robert Beers, Rajnish Ghughal, Mark Aagaard

      Pages 1-19

3. Invited Talk

   1. Trends in Computing

      • Mark E. Dean

      Pages 20-21

4. Invited Paper

   1. A Case Study in Formal Verification of Register-Transfer Logic with ACL2: The Floating Point Adder of the AMD Athlon ^TM Processor

      • David M. Russinoff

      Pages 22-55

5. Contributed Papers

   1. An Algorithm for Strongly Connected Component Analysis in n log n Symbolic Steps

      • Roderick Bloem, Harold N. Gabow, Fabio Somenzi

      Pages 56-73

   2. Automated Refinement Checking for Asynchronous Processes

      • Rajeev Alur, Radu Grosu, Bow-Yaw Wang

      Pages 74-91

   3. Border-Block Triangular Form and Conjunction Schedule in Image Computation

      • In-Ho Moon, Gary D. Hachtel, Fabio Somenzi

      Pages 92-109

   4. B2M: A Semantic Based Tool for BLIF Hardware Descriptions

      • David Basin, Stefan Friedrich, Sebastian Mödersheim

      Pages 110-126

   5. Checking Safety Properties Using Induction and a SAT-Solver

      • Mary Sheeran, Satnam Singh, Gunnar Stålmarck

      Pages 127-144

   6. Combining Stream-Based and State-Based Verification Techniques

      • Nancy A. Day, Mark D. Aagaard, Byron Cook

      Pages 145-161

   7. A Comparative Study of Symbolic Algorithms for the Computation of Fair Cycles

      • Kavita Ravi, Roderick Bloem, Fabio Somenzi

      Pages 162-179

   8. Correctness of Pipelined Machines

      • Panagiotis Manolios

      Pages 181-198

   9. Do You Trust Your Model Checker?

      • Wolfgang Reif, Jürgen Ruf, Gerhard Schellhorn, Tobias Vollmer

      Pages 199-216

   10. Executable Protocol Specification in ESL

       • E. Clarke, S. German, Y. Lu, H. Veith, D. Wang

       Pages 217-236

   11. Formal Verification of Floating Point Trigonometric Functions

       • John Harrison

       Pages 254-270

   12. Hardware Modeling Using Function Encapsulation

       • Jun Sawada, Warren A. Hunt Jr

       Pages 271-282

   13. A Methodology for the Formal Analysis of Asynchronous Micropipelines

       • Antonio Cerone, George J. Milne

       Pages 283-299

   14. A Methodology for Large-Scale Hardware Verification

       • Mark D. Aagaard, Robert B. Jones, Thomas F. Melham, John W. O’Leary, Carl-Johan H. Seger

       Pages 300-319

   15. Model Checking Synchronous Timing Diagrams

       • Nina Amla, E. Allen Emerson, Robert P. Kurshan, Kedar S. Namjoshi

       Pages 320-335

   16. Model Reductions and a Case Study

       • Jin Hou, Eduard Cerny

       Pages 336-352

The biannual Formal Methods in Computer Aided Design conference (FMCAD 2000)is the third in a series of conferences under that title devoted to the use of discrete mathematical methods for the analysis of computer hardware and so- ware. The work reported in this book describes the use of modeling languages and their associated automated analysis tools to specify and verify computing systems. Functional veric ation has become one of the principal costs in a modern computer design e ort. In addition,verica tion of circuit models, timing,power, etc., requires even more eo rt. FMCAD provides a venue for academic and - dustrial researchers and practitioners to share their ideas and experiences of using discrete mathematical modeling and veric ation. It is noted with interest by the conference chairmen how this area has grown from just a few people 15 years ago to a vibrant area of research, development, and deployment. It is clear that these methods are helping reduce the cost of designing computing systems. As an example of this potential cost reduction, we have invited David Russino of Advanced Micro Devices, Inc. to describe his veric ation of ?oating-point - gorithms being used in AMD microprocessors. The program includes 30 regular presentations selected from 63 submitted papers.

• Automat
• computer-aided design (CAD)
• formal method
• formal specification
• formal verification
• model
• model checking
• modeling
• proving
• semantics
• simulation
• theorem proving
• verification
• complexity

• Austin Research Laboratories, IBM Corporation, Texas, USA

  Warren A. Hunt

• Computer Science Department, Indiana University, Indiana, USA

  Steven D. Johnson

Policies and ethics