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