Generating a test suite from an abstract state machine

1. A method of generating a data structure representing a finite state machine (FSM) in a computer memory, the method comprising:

generating a first encoding corresponding to a first state of an abstract state machine (ASM), the encoding generated from an evaluation of non-trivial guard conditions of the ASM; and

when the first encoding is not the same as any encoding already associated with a state of the FSM, including data associating the first encoding with the first state in the data structure representing the FSM.

2. The method of claim 1 wherein generating the encoding further comprises:

evaluating non-trivial guard conditions of the ASM;

representing the result of each evaluation with a first value in the encoding when the evaluation is true; and

representing the result of each evaluation with a second value in the encoding otherwise.

3. The method of claim 1 wherein the ASM has a normalized form.

4. The method of claim 1 further comprising:

performing at least one actions of the ASM on the first state to generate at least one state transitions to at least one other ASM states;

generating at least one other encodings, each other encoding corresponding to one of the at least one other ASM states; and

when one of the other encodings is not the same as any one of the encodings already associated with a state of the FSM, including data representing the one of the other encodings and the corresponding state in the data structure representing the FSM.

5. The method of claim 4 further comprising:

concluding generation of the data structure when each of the at least one other encodings is the same as any one of the encodings already associated with a state of the FSM.

6. A method of generating a data structure representing a finite state machine (FSM) in a computer memory, the method comprising:

selecting an initial state of an abstract state machine (ASM);

generating a first encoding comprising a plurality of bits to represent the initial state, each bit of the first encoding representing a result of an evaluation of a non-trivial guard condition of the ASM;

associating the initial state with the first encoding in the data structure for the FSM;

identifying at least one other states of the ASM that result from applying at least one actions of the ASM to the initial state;

generating at least one other encodings, each of the at least one other encodings corresponding to one of the at least one other states; and

for each one of the at least one other states, including data in the data structure associating the one of the at least one other states and a corresponding of the at least one other encodings when the corresponding of the at least one other encodings is not the same as the any one encoding already associated with a state in the data structure.

7. The method of claim 6 further comprising:

including in the data structure data representing an action that results in a transition from the first state to one of the at least one other states.

8. The method of claim 6 wherein the ASM has a normalized form.

9. An article comprising:

a machine-readable medium comprising instructions to generate a data structure representing a finite state machine (FSM) in a computer memory, the instructions, when executed by a computer system, resulting in:

generating a first encoding corresponding to a first state of an abstract state machine (ASM), the encoding generated from an evaluation of non-trivial guard conditions of the ASM; and

when the first encoding is not the same as any encoding already associated with a state of the FSM, including data associating the first encoding with the first state in the data structure representing the FSM.

10. The article of claim 9 wherein the instructions, when executed by the computer system, result in:

evaluating non-trivial guard conditions of the ASM;

representing the result of each evaluation with a first value in the encoding when the evaluation is true; and

representing the result of each evaluation with a second value in the encoding otherwise.

11. The article of claim 9 wherein the instructions, when executed by the computer system, operate upon the ASM in a normalized form.

12. The article of claim 9 wherein the instructions, when executed by the computer system, result in:

performing at least one actions of the ASM on the first state to generate at least one state transitions to at least one other ASM states;

generating at least one other encodings, each other encoding corresponding to one of the at least one other ASM states; and

when one of the other encodings is not the same as any one of the encodings already associated with a state of the FSM, including data representing the one of the other encodings and the corresponding state in the data structure representing the FSM.

13. The article of claim 9 wherein the instructions, when executed by the computer system, result in:

concluding generation of the data structure when each of the at least one other encodings is the same as any one of the encodings already associated with a state of the FSM.

14. An article comprising:

a machine-readable medium comprising instructions to generate a data structure representing a finite state machine (FSM) in a computer memory, the instructions, when executed by a computer system, resulting in:

selecting an initial state of an abstract state machine (ASM);

generating a first encoding comprising a plurality of bits to represent the initial state, each bit of the first encoding representing a result of an evaluation of a non-trivial guard condition of the ASM;

associating the initial state with the first encoding in the data structure for the FSM;

identifying at least one other states of the ASM that result from applying at least one actions of the ASM to the initial state;

generating at least one other encodings, each of the at least one other encodings corresponding to one of the at least one other states; and

for each one of the at least one other states, including data in the data structure associating the one of the at least one other states and a corresponding of the at least one other encodings when the corresponding of the at least one other encodings is not the same as the any one encoding already associated with a state in the data structure.

15. The article of claim 14 wherein the instructions, when executed by the computer system, result in:

including in the data structure data representing an action that results in a transition from the first state to one of the at least one other states.

16. The article of claim 14 wherein the instructions, when executed by the computer system, operate upon the ASM in a normalized form.

17. An apparatus comprising:

a processor; and

a machine-readable medium comprising instructions to generate a data structure representing a finite state medium (FSM) in a computer memory, the instructions, when executed by a computer system comprising the processor, resulting in:

generating a first encoding corresponding to a first state of an abstract state machine (ASM), the encoding generated from an evaluation of non-trivial guard conditions of the ASM; and

when the first encoding is not the same as any encoding already associated with a state of the FSM, including data associating the first encoding with the first state in the data structure representing the FSM.

18. The apparatus of claim 17 wherein the instructions, when executed by the computer system, result in:

evaluating non-trivial guard conditions of the ASM;

representing the result of each evaluation with a first value in the encoding when the evaluation is true; and

representing the result of each evaluation with a second value in the encoding otherwise.

19. The apparatus of claim 17 wherein the instructions, when executed by the computer system, operate upon the ASM in a normalized form.

20. The apparatus of claim 17 wherein the instructions, when executed by the computer system, result in:

performing at least one actions of the ASM on the first state to generate at least one state transitions to at least one other ASM states;

generating at least one other encodings, each other encoding corresponding to one of the at least one other ASM states; and

when one of the other encodings is not the same as any one of the encodings already associated with a state of the FSM, including data representing the one of the other encodings and the corresponding state in the data structure representing the FSM.

21. The apparatus of claim 17 wherein the instructions, when executed by the computer system, result in:

concluding generation of the data structure when each of the at least one other encodings is the same as any one of the encodings already associated with a state of the FSM.

22. An article comprising:

a processor; and

a machine-readable medium comprising instructions to generate a data structure representing a finite state machine (FSM) in a computer memory, the instructions, when executed by a computer system comprising the processor, resulting in:

selecting an initial state of an abstract state machine (ASM);

generating a first encoding comprising a plurality of bits to represent the initial state, each bit of the first encoding representing a result of an evaluation of a non-trivial guard condition of the ASM;

associating the initial state with the first encoding in the data structure for the FSM;

identifying at least one other states of the ASM that result from applying at least one actions of the ASM to the initial state;

generating at least one other encodings, each of the at least one other encodings corresponding to one of the at least one other states; and

for each one of the at least one other states, including data in the data structure associating the one of the at least one other states and a corresponding of the at least one other encodings when the corresponding of the at least one other encodings is not the same as the any one encoding already associated with a state in the data structure.

23. The apparatus of claim 22 wherein the instructions, when executed by the computer system, result in:

including in the data structure data representing an action that results in a transition from the first state to one of the at least one other states.