On the possibilities of FSM description of Parallel composition of Timed Finite State Machines

Abstract

Finite State Machines (FSMs) are widely used for analysis and synthesis of digital components of control systems. In order to take into account time aspects, timed FSMs are considered. In this paper, we address the problem of deriving a parallel composition of two types of Timed Finite State Machines (TFSM), namely, FSMs with timeouts and FSMs with timed guards. These two TFSM types are not interchangeable and are particular cases of a more general TFSM model that has timeouts and timed guards. We also assume that all of considered TFSMs have output delays (output timeouts). When considering the parallel composition, component FSMs work in the dialog and the composition produces an external output when interaction between components is finished. In this work, it is shown that in the general case, unlike classical FSMs, a "slow environment" and the absence of livelocks are not enough for describing the behavior of a composition by a complete deterministic FSM with a single clock. The latter occurs when inputs can be applied to TFSMs not only at integer time instances but also at rational. A class of systems for which the behavior can be described by a complete deterministic TFSM is specified. Those are systems where both component TFSMs are participating in the dialog when an external input is applied; a sequential composition of TFSMs is a particular case of such composition.