Minimizing Symbolic Finite Automata

摘要

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.

主权项

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, andselecting 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.