Proceedings of ISP RAS

On the minimization of timed Finite State Machines.

Alexandre Tvardovskiy.


This paper addresses the problem of minimizing a Finite State Machine (FSM) augmented with input and output timeouts, since almost all methods for deriving complete test suites are developed for reduced (minimal) timed machines, i.e., FSMs where every two states are not equivalent. If at some state no input is applied until the corresponding (input) timeout expires then the FSM can spontaneously move to another prescribed state. An output timeout describes the time that is necessary for executing a transition that is the number of time instances needed for producing an output after an input has been applied. A technique for minimizing such machines based on corresponding classical FSMs is proposed; it is also shown that differently from classical FSMs, an FSM with timeouts can have minimal forms which are not pair-wise isomorphic.


FSM minimization, input and output timeouts, minimal (reduced) form


Proceedings of the Institute for System Programming, vol. 26, issue 6, 2014, pp. 77-84

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2014-26(6)-7

Full text of the paper in pdf (in Russian) Back to the contents of the volume