Optimal test generation for finite state machine models

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.