Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2006-06-06
2006-06-06
Thompson, A. M. (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
07058910
ABSTRACT:
An invariant checking method and apparatus using binary decision diagrams (BDDs) in combination with constraint solvers for determining whether a system property is an invariant of a system description. The invariant checking method receives system descriptions and system properties and transforms them into a model formula. Specific variables are eliminated from the model formula and a corresponding output formula is generated. The output formula is transformed into a logic formula by substituting a new logic variable for each integer constraint in the output formula. A constrained BDD is constructed from the logic formula. The constrained BDD uses a heuristic algorithm to order the logic variables in the paths leading to true or false. A constraint solver is applied to the integer constraints that correspond to the occurrences of logic variables in the BDD paths, which determines whether the system property is or is not an invariant of the system description.
REFERENCES:
patent: 5390325 (1995-02-01), Miller
patent: 5481717 (1996-01-01), Gaboury
patent: 5513122 (1996-04-01), Cheng et al.
patent: 5652835 (1997-07-01), Miller
patent: 5680332 (1997-10-01), Raimi et al.
patent: 5752000 (1998-05-01), McGeer et al.
patent: 5910897 (1999-06-01), Dangelo et al.
patent: 5987252 (1999-11-01), Leino et al.
patent: 6026222 (2000-02-01), Gupta et al.
patent: 6131078 (2000-10-01), Plaisted
patent: 6212669 (2001-04-01), Jain
patent: 6275976 (2001-08-01), Scandura
patent: 6728665 (2004-04-01), Gupta et al.
Bharadwaj et al, Salsa: Combining Constraint Solvers with BDD'S for Automatic Invariant Checking, in Proc. Tools and Algorithms for the Construction and Analysis of Systems, (TACAS 2000). Lecture Notes in Computer Science, Springer, pp. 1-16.
Bharadwaj Ramesh
Sims Steve
Bowers Brandon
Karasek John J.
Legg L. George
The United States of America as represented by the Secretary of
Thompson A. M.
LandOfFree
Invariant checking method and apparatus using binary... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Invariant checking method and apparatus using binary..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Invariant checking method and apparatus using binary... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3630630