Proceedings of ISP RAS

Experiments on Parallel Composition of Timed Finite State Machines

A. Sotnikov (TSU, Tomsk, Russia)
N. Shabaldina (TSU, Tomsk, Russia)
M. Gromov (TSU, Tomsk, Russia)


In this paper, we continue our work that is devoted to the parallel composition of Timed Finite State Machines (TFSMs). We consider the composition of TFSMs with timeouts and output delays. We held experiments in order to estimate how often parallel composition of nondeterministic TFSMs (with and without timeouts) has infinite sets of output delays. To conduct these experiments we have created two tools: the first one for converting TFSMs into automata (this tool is integrated into BALM-II), the second one for converting the global automaton of the composition into TFSM. As it was suggested in earlier works, we describe the infinite sets of output delays by linear functions, and it is important to know how often these sets of linear functions appear to justify the importance of future investigations of the TFSM parallel compositions (especially for deriving cascade composition). Results of the experiments show significant amount (around 50 %) of TFSMs with infinite number of output delays. We also estimate the size of the global automaton and the composed TFSM. In the experiments, we do not consider global automata with the huge number of states (more then 10000).


Timed finite state machine; parallel composition; BALM-II


Proceedings of the Institute for System Programming, vol. 29, issue 3, 2017, pp. 233-246.

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

DOI: 10.15514/ISPRAS-2017-29(3)-13

Full text of the paper in pdf Back to the contents of the volume