Lazy symbolic model checking
US6725431B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | Jun 30, 2000 |
| Grant date | Apr 20, 2004 |
| Priority date | — |
| Expiry date | Jun 9, 2022 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F30/3323
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Methods for formal verification of circuits and other finite-state systems may improve efficiency and capacity of popular binary decision diagram (BDD) based algorithms. A lazy pre-image computation method builds new transition relation partitions on-demand only for relevant next internal variables of a state predicate, and conjoins only next state relations for relevant next internal variables to a pre-image including the state predicate. A lazy backward reachability analysis method makes iterative use of the lazy pre-image computation method to compute the set of states reachable to a given set of states in zero or more transitions. A lazy equivalence checking method makes iterative use of the lazy pre-image computation method to compute conditions that necessarily must be satisfied to disprove equivalence. These methods may provide for symbolic model checking of circuits and other finite state systems previously too large to be completed successfully using BDD based algorithms.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.