Model checking and abstraction
Edmund M. Clarke, Orna Grümberg, David E. Long · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · 1992
We describe a method for using abstraction to reduce the complexity of temporal logic model checking. The basis of this method is a way of constructing an abstract model of a program without ever examining the corresponding unabstracted model. We show how this abstract model can be used to verify properties of the original program. We have implemented a system based on these techniques, and we demonstrate their practicality using a number of examples, including a pipelined ALU circuit with over 101300 states.
Cited by 352 works. doi:10.1145/143165.143235 Open-access PDF
Authors
References
- Graph-Based Algorithms for Boolean Function Manipulation
- Automatic verification of finite-state concurrent systems using temporal logic specifications
- Design and synthesis of synchronization skeletons using branching time temporal logic
- Assigning Meanings to Programs
- Specification and verification of concurrent systems in CESAR
- Sequential circuit verification using symbolic model checking
- The complexity of propositional linear temporal logics
- Checking that finite state concurrent programs satisfy their linear specification
- Automatic verification of finite state concurrent system using temporal logic specifications
- Evaluation and improvement of Boolean comparison method based on binary decision diagrams