The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Apr. 27, 2004
Filed:
Oct. 23, 2000
Aarti Gupta, Princeton, NJ (US);
Zijiang Yang, Plainsboro, NJ (US);
Pranav Ashar, Princeton, NJ (US);
NEC Corporation, Tokyo, JP;
Abstract
A method of performing image or pre-image computation for a system is disclosed. The method comprises representing the system by a finite state model; representing state sets using Binary Decision Diagrams (BDDs); performing a satisfiabilty checking (SAT) based backtrack search algorithm, wherein, the SAT decomposes the search over an entire solution space into multiple sub-problems, and wherein a BDD-based image computation is used to solve each sub-problem by enumerating multiple solutions from the solution space. Further, a method for pruning a search space in a SAT procedure is disclosed. The method comprises using BDD Bounding against an implicit disjunction or conjunction of a given set of BDDs; continuing search if a partial assignment of variables satisfies the implicit disjunction or conjunction, and backtracking if a partial assignment of variables does not satisfy the implicit disjunction or conjunction.