Data processing: structural design – modeling – simulation – and em – Modeling by mathematical expression
Reexamination Certificate
2006-08-15
2006-08-15
Paladini, Albert W. (Department: 2125)
Data processing: structural design, modeling, simulation, and em
Modeling by mathematical expression
C709S224000, C717S124000
Reexamination Certificate
active
07092858
ABSTRACT:
In a finite state machine (FSMverify) a set of goal states, to be searched for their reachability from a start state, is defined.An overapproximated path is found from a start state to a goal state by a forward approximation technique. The overapproximated path representation relies upon a partitioning of the state and input bits of FSMverify. A state matrix of the overapproximated path is organized by time-steps of FSMverifyalong a first dimension and by partitions of FSMverifystate bits along a second dimension.An underapproximated path, along the path of the stepping stone matrix, is determined. Underapproximation is typically accomplished by simulation.A sequence of states to be output is updated with the underapproximated path.If a start to goal state sequence has been found, the procedure ends. Otherwise, the above steps of over and under approximation are repeated, using the results of the last underapproximation as a start state.
REFERENCES:
patent: 5963447 (1999-10-01), Kohn et al.
patent: 6275976 (2001-08-01), Scandura
patent: 6289502 (2001-09-01), Garland et al.
patent: 6668203 (2003-12-01), Cook et al.
patent: 6789116 (2004-09-01), Sarkissian et al.
H. Cho, G. D. Hachtel, E. Macii, B. Plessier, and F. Somenzi. “Algorithms for Approximate FSM Traversal.” Proc. 30th ACM/IEEE Design Automation Conference, pp. 25-30, 1993.
H. Cho, G. D. Hachtel, E. Macii, M. Poncino, and F. Somenzi. “A Structural Approach to State Space Decomposition for Approximate Reachability Analysis.” In Proc. IEEE Intl. Conf. on Computer Design (ICCD), Oct. 10-12, 1994, pp236-239.
H. Cho, G. D. Hachtel, E. Macii, M. Poncino, and F. Somenzi. “Automatic State Space Decomposition for Approximate FSM Traversal Based on Circuit Analysis.” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, No. 12, Dec. 1996, pp1451-1464.
H. Cho, G. D. Hachtel, E. Macii, B. Plessier, and F. Somenzi. “Algorithms for Approximate FSM Traversal Based on State Space Decomposition.” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, No. 12, Dec. 1996, pp1465-1478.
C. H. Yang and D. L. Dill. “Validation with Guided Search of the State Space.” In Proc. of the Design Automation Conf., Jun. 1998, pp599-604.
Govindaraju, G. S. and Dill. D. L. “Verification by Approximate Forward and Backward Reachability.” IEEE/ACM ICCAD, pp. 366-370, Nov. 8-12, 1998.
Jun Yuan, Jian Shen, Jacob Abraham, and Adnan Aziz, “On Combining Formal and Informal Verification,” in Proceedings of Conference on Computer-Aided Verification. Haifa. ISRAEL, Jul. 1997. 12 pages.
Kukula James Herbert
Ranjan Rajeev Kumar
Shiple Thomas Robert
Kaplan Jonathan T.
Paladini Albert W.
Synopsys Inc.
LandOfFree
Method and apparatus for formally constraining random... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for formally constraining random..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for formally constraining random... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3679285