The problem of describing the behavior of communicating discrete event systems arises in a number of applications. Many discrete systems can be considered as systems transforming input sequences of actions in one alphabet into output sequences in another alphabet. Often for analysis and synthesis of such systems it is important to take into account time aspects of their behavior, and hence, develop appropriate models. In this paper, we consider the composition of discrete event systems interacting in an asynchronous (parallel) mode taking into account their timeout properties. Finite state models are widely used for discrete event system synthesis and analysis, and in this paper, we use the notion of a Finite State Machine (FSM) with timeouts when describing the system behavior. A Finite State Machine with timeouts, or simply a Timed Finite State Machine (TFSM) throughout the paper, is an initialized FSM augmented with an input timeout function and an output timeout function. The input timeout function specifies the maximal time of waiting for an input for each state, and the next state where the TFSM moves to if no input has been applied before the timeout expires. The output timeout function (often referred to as an output delay function) specifies the number of time instances needed for the TFSM to process an applied input and produce a corresponding output. The set of traces of the TFSM is represented as that of a proper deterministic finite automaton in a following way: a corresponding automaton Aut(S) accepts a trace alpha = 1(t1)[i(1)1(k1) o(1) ... 1(tm) i(m) 1(km) o(m)](p), if and only if p = or p = 1 and 'i(1), t(1)'/'o(1), k(1)' ... 'i(m), t(m)'/'o(m), k(m)' is a time trace of the given TFSM S. To derive such automaton, each TFSM transition is unfolded into a chain of consecutive transitions and there is a corresponding chain of transitions between an input and output symbols labeled by a special symbol 1 (which represents an action "to wait for one time unit") according to the timeout functions. In the parallel composition, the components communicate in a dialogue mode and as usual, Finite State Machines communicate under the assumption of a "slow environment". In other words, the next input is applied only after the composition has produced an output to the previous input. The parallel composition of two TFSMs is defined through the operations over corresponding finite automata: given the component TFSMs S and P, the composition TFSM C = S (sic) P is the machine that has the corresponding automaton Aut(C) = [Aut(S) (sic) Aut(P)] boolean AND Aut(T-I,T-O), where T-I,T-O = [(1)* I(1)* O]*(1)* represents the language containing all the TFSM languages (in other words, the language accepted by the union of all the corresponding automata). The set of deterministic TFSMs is shown to be closed under parallel composition, i.e., the composition of deterministic
