1997 · 35 citations · 9 references
ComputingComputer EngineeringComputer ScienceAlgorithmsFormal MethodsTheory Of ComputationDeductive VerificationFinite State Machine ModelingModel CheckingVerificationDepth-first SearchForward CheckingState Space ExplorationState-space StructureSymbolic Model CheckingTransition Systems
Forward model checking is an efficient symbolic model checking method for verifying realistic properties of sequential circuits and protocols. In this paper, we present the techniques that modify the order of state traversal on forward model checking, and that dramatically improve average CPU time for finding design errors. A failing property has to be checked again and again to analyze the bug until it is corrected. The techniques, therefore, can have significant impacts on actual verification tasks. We use a modified regular/!-regular expression to represent a set of illegal state transition sequences of an FSM. It makes the problem clear and gives us a sense of depth-first traversal, not on the state space, but on the property. 1
9
Graph-Based Algorithms for Boolean Function Manipulation
Bryant · IEEE Transactions on Computers · 1986 · 8.9K citations · Full text
Symbolic model checking: 1020 States and beyond
Jerry R. Burch, E. M. Clarke, Kenneth L. McMillan et al. · Information and Computation · 1992 · 2.7K citations
Sequential circuit verification using symbolic model checking
Jerry R. Burch, E. M. Clarke, Kenneth L. McMillan et al. · 1990 · 413 citations · Full text
Efficient generation of counterexamples and witnesses in symbolic model checking
E. M. Clarke, Orna Grümberg, Kenneth L. McMillan et al. · 1995 · 220 citations · Full text