Techniques are provided herein for minimizing symbolic finite automata. The techniques for minimizing symbolic finite automata include the selection of a set of states, which may include a set of final states or a set of non-final states. By following the transitions from the selected states, techniques disclosed herein define partitions between various states of the SFA. Techniques are applied to the states in each partition to determine the states and state transitions of a minimized symbolic finite automaton. Techniques disclosed herein allow for the minimization of a symbolic finite automaton without the need to calculate minterms.
Please help me write a proper abstract based on the patent claims. CLAIM: 1. In a computing environment, a method performed at least in part by a processor, comprising: obtaining data defining a symbolic finite automaton, wherein the symbolic finite automaton includes a plurality of states, the plurality of states include at least one final state and at least one non-final state; selecting at least one state of the plurality of states to be included in an initial partition, wherein the initial partition includes the at least one final state or the at least one non-final state; selecting a second set of states from the plurality of states to be included in a second partition, wherein individual states of the second set of states have transitions that lead to the at least one state included in the initial partition; if a predicate of at least one individual state of the second set of states is not equivalent to a predicate of another individual state of the second set of states, refining the second partition to create a first refining partition, and selecting at least one individual state of the second set of states to be included in the first refining partition; and generating a minimized symbolic finite automaton by unionizing the states included in the individual partitions. 2. The method of claim 1, further comprising, determining if a number of final states is equal to or fewer than a number of non-final states, and wherein the initial partition includes the at least one final state if the number of final states is equal to or fewer than the number of non-final states. 3. The method of claim 1, further comprising, determining if a number of non-final states is fewer than a number of final states, and wherein the initial partition includes the at least one non-final state if the number of non-final states is fewer than the number of final states. 4. The method of claim 1, further comprising: selecting a third set of states of the plurality of states to be included in a third partition, wherein individual states of the third set of states have transitions that lead to at least one state included in the second partition or the first refining partition; if a predicate of at least one individual state of the third set of states is not equivalent to a predicate of another individual state of the third set of states, refining the third partition to create a refining partition of the third partition, and selecting at least one individual state of the third set of states to be included in the refining partition of the third partition. 5. The method of claim 1, wherein the second set of states comprises a second state associated with a second predicate and a third state associated with a third predicate, wherein the second predicate and the third predicate are not equivalent to the predicate of at least one individual state of the second set of states, and wherein the method further comprises: if the second predicate is not equivalent to the third predicate, refining the second partition to create a second refining partition, and selecting the second state or the third state to be included in the second refining partition. 6. The method of claim 1, wherein the at least one individual state of the second set of states to be included in the first refining partition includes a plurality of selected states from the second set of states, wherein the individual states of the plurality of selected states have equivalent predicates. 7. The method of claim 1, wherein unionizing the states included in the individual partitions comprises normalizing the predicates of the second set of states to define a predicate of a state of the minimized symbolic finite automaton, wherein a transition of the state of the minimized symbolic finite automaton leads to at least one final state. 8. A computer-readable storage medium having computer-executable instructions stored thereupon which, when executed by a computing device, cause the computing device to: obtain data defining a symbolic finite automaton, wherein the symbolic finite automaton includes a plurality of states, the plurality of states include at least one final state and at least one non-final state; select at least one state of the plurality of states to be included in an initial partition, wherein the initial partition includes the at least one final state or the at least one non-final state; select a second set of states from the plurality of states to be included in a second partition, wherein individual states of the second set of states have transitions that lead to the at least one state included in the initial partition; if a predicate of at least one individual state of the second set of states is not equivalent to a predicate of another individual state of the second set of states, refine the second partition to create a first refining partition, and select at least one individual state of the second set of states to be included in the first refining partition; and generate a minimized symbolic finite automaton by unionizing the states included in the individual partitions. 9. The computer-readable storage medium of claim 8, wherein the computer-executable instructions further cause the computing device to determine if a number of final states is equal to or fewer than a number of non-final states, and wherein the initial partition includes the at least one final state if the number of final states is equal to or fewer than the number of non-final states. 10. The computer-readable storage medium of claim 8, wherein the computer-executable instructions further cause the computing device to determine if a number of non-final states is fewer than a number of final states, and wherein the initial partition includes the at least one non-final state if the number of non-final states is fewer than the number of final states. 11. The computer-readable storage medium of claim 8, wherein the computer-executable instructions further cause the computing device to: select a third set of states of the plurality of states to be included in a third partition, wherein individual states of the third set of states have transitions that lead to at least one state included in the second partition or the first refining partition; and if a predicate of at least one individual state of the third set of states is not equivalent to a predicate of another individual state of the third set of states, refine the third partition to create a refining partition of the third partition, and select at least one individual state of the third set of states to be included in the refining partition of the third partition. 12. The computer-readable storage medium of claim 8, wherein the second set of states comprises a second state associated with a second predicate and a third state associated with a third predicate, wherein the second predicate and the third predicate are not equivalent to the predicate of at least one individual state of the second set of states, and wherein the computer-executable instructions further cause the computing device to: if the second predicate is not equivalent to the third predicate, refine the second partition to create a second refining partition, and select the second state or the third state to be included in the second refining partition. 13. The computer-readable storage medium of claim 8, wherein the at least one individual state of the second set of states to be included in the first refining partition includes a plurality of selected states from the second set of states, and wherein the individual states of the plurality of selected states have equivalent predicates. 14. The computer-readable storage medium of claim 8, wherein unionizing the states included in the individual partitions comprises normalizing the predicates of the second set of states to define a predicate of a state of the minimized symbolic finite automaton, and wherein a transition of the state of the minimized symbolic finite automaton leads to at least one final state. 15. A computing device, comprising: a processor; and a computer-readable storage medium in communication with the processor, the computer-readable storage medium having computer-executable instructions stored thereupon which, when executed by the processor, cause the processor to obtain data defining a symbolic finite automaton, wherein the symbolic finite automaton includes a plurality of states, the plurality of states include at least one final state and at least one non-final state; select at least one state of the plurality of states to be included in an initial partition, wherein the initial partition includes the at least one final state or the at least one non-final state; select a second set of states from the plurality of states to be included in a second partition, wherein individual states of the second set of states have transitions that lead to the at least one state included in the initial partition; if a predicate of at least one individual state of the second set of states is not equivalent to a predicate of another individual state of the second set of states, refine the second partition to create a first refining partition, and select at least one individual state of the second set of states to be included in the first refining partition; and generate a minimized symbolic finite automaton by unionizing the states included in the individual partitions. 16. The computer-readable storage medium of claim 15, wherein the computer-executable instructions further cause the processor to determine if a number of final states is equal to or fewer than a number of non-final states, and wherein the initial partition includes the at least one final state if the number of final states is equal to or fewer than the number of non-final states. 17. The computing device of claim 15, wherein the computer-executable instructions further cause the processor to determine if a number of non-final states is fewer than a number of final states, and wherein the initial partition includes the at least one non-final state if the number of non-final states is fewer than the number of final states. 18. The computing device of claim 15, wherein the computer-executable instructions further cause the processor to: select a third set of states of the plurality of states to be included in a third partition, wherein individual states of the third set of states have transitions that lead to at least one state included in the second partition or the first refining partition; and if a predicate of at least one individual state of the third set of states is not equivalent to a predicate of another individual state of the third set of states, refine the third partition to create a refining partition of the third partition, and select at least one individual state of the third set of states to be included in the refining partition of the third partition. 19. The computing device of claim 15, wherein the second set of states comprises a second state associated with a second predicate and a third state associated with a third predicate, wherein the second predicate and the third predicate are not equivalent to the predicate of at least one individual state of the second set of states, and wherein the computer-executable instructions further cause the processor to: if the second predicate is not equivalent to the third predicate, refine the second partition to create a second refining partition, and select the second state or the third state to be included in the second refining partition. 20. The computing device of claim 15, wherein the at least one individual state of the second set of states to be included in the first refining partition includes a plurality of selected states from the second set of states, and wherein the individual states of the plurality of selected states have equivalent predicates.