US4991176A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Optimal test generation for finite state machine models
Assignee: Nokia Bell Labs
•
Filing: 1989-06-07
•
Granted: 1991-02-05
•
Expires: 2009-06-07
Abstract
Abstract Faster, yet, completely efficient and exhaustive testing is afforded an entity (e.g., protocol, VLSI circuit, software application) represented as finite state machines by employing the present method in which test sequences are generated according to minimum cost function rules. Minimum cost unique signatures are developed for state identification of the finite state machine. Based upon the minimum cost unique signatures, a minimum cost test sequence is generated to cover every state transition of the finite state machine. As a result, every testable aspect of the entity is guaranteed to be tested using a minimum number of steps which represents a considerable cost savings.
Inventors
- 👤 Anton T. Dahbura
- 👤 Krishan K. Sabnani
- 👤 M. Umit Uyar
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 12:11
CPC Classifications
G; G01; G01R; G01R31/00; G01R31/28; G01R31/317; G01R31/3181; G01R31/3183; G01R31/318342; G01R31/318357; G01R31/318371; G06; G06F; G06F30/00; G06F30/30; G06F30/32; G06F30/33; G06F30/3323; G06F7/00
Claims Analysis
Total Claims: 2
Claim 1
Independent Claim
173 words
A method for developing test sequences for evaluating a design or operation of a finite state machine, said finite state machine characterized by a state diagram having states and original edges interconnecting the states, said method comprising the steps of: evaluating unique input/output sequences for each state of said finite state machine so that the unique input/output sequence selected for each state exhibits a minimum cost among all unique input/output sequences evaluated for that state; expanding said state diagram as a test graph including said states, said original edges, and a plurality of test edges interconnecting the states, said plurality of test edges for testing original edges of the state diagram; evaluating said test graph for symmetry and, if not symmetric, duplicating selected test edges of said plurality to make said test graph symmetric with a minimum cost; and generating a tour of the symmetric test graph wherein each test edge is traversed at least once, so that said tour includes said test sequence for said finite state machine at a minimum cost.
Claim 2
Independent Claim
173 words
A method for developing test sequences for evaluating a design or operation of a finite state machine, said finite state machine characterized by a state diagram having states and original edges interconnecting the states, said method comprising the steps of: evaluating unique input/output sequences for each state of said finite state machine so that the unique input/output sequence selected for each state exhibits a minimum cost among all unique input/output sequences evaluated for that state; expanding said state diagram as a test graph including said states, said original edges, and a plurality of test edges interconnecting the states, said plurality of test edges for testing original edges of the state diagram; evaluating said test graph for symmetry and, if not symmetric, duplicating selected test edges of said plurality to make said test graph symmetric with a minimum cost; and generating a tour of the symmetric test graph wherein each test edge is traversed at least once, so that said tour includes said test sequence for said finite state machine at a minimum cost.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-02-04 | 1994-08-06 | 1995-02-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-02-04 | 1998-08-06 | 1999-02-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-02-04 | 2002-08-06 | 2003-02-05 | $7700.00 | Window Closed / Lapsed |