Minimizing timed Finite State Machines

Finite State Machines (FSM) are widely used for analysis and synthesis of discrete event systems. However, for systems for which timed aspects are important, the notion of a classical FSM has to be extended. One of such extensions is to take into account time guards for inputs and timeouts for outputs. Correspondingly, the behavior of such FSM depends on a time instance when an input is applied; and moreover, the output timeout specifies the time duration that is needed for processing a given input. In this paper, we solve the problem of minimizing such timed FSM (TFSM). We discuss appropriate properties of TFSMs; the notion of k-equivalent and equivalent states and a reduced (minimal) form are introduced. The TFSM minimization is based on the deriving partitions for k-equivalent states which can be refined at the next step. In other words, the clauses of the partition for (k+1)-equivalent states are subsets of those for k-equivalent states. If the refined partition equals the previous one then the derived partition corresponds to the equivalence relation and its clauses can be selected as states of the corresponding reduced TFSM. We show that a reduced form for a TFSM is unique up to isomorphism.

Keywords

Authors

References