On the possibilities of FSM description of Parallel composition of Timed Finite State Machines
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 Machine...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ivannikov Institute for System Programming of the Russian Academy of Sciences
2018-10-01
|
| Series: | Труды Института системного программирования РАН |
| Subjects: | |
| Online Access: | https://ispranproceedings.elpub.ru/jour/article/view/451 |
| _version_ | 1818110304419053568 |
|---|---|
| author | A. S. Tvardovskii A. V. Laputenko |
| author_facet | A. S. Tvardovskii A. V. Laputenko |
| author_sort | A. S. Tvardovskii |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-11T02:45:01Z |
| format | Article |
| id | doaj.art-6ee4b06eb1d048aa92c96f66ed853973 |
| institution | Directory Open Access Journal |
| issn | 2079-8156 2220-6426 |
| language | English |
| last_indexed | 2024-12-11T02:45:01Z |
| publishDate | 2018-10-01 |
| publisher | Ivannikov Institute for System Programming of the Russian Academy of Sciences |
| record_format | Article |
| series | Труды Института системного программирования РАН |
| spelling | doaj.art-6ee4b06eb1d048aa92c96f66ed8539732022-12-22T01:23:28ZengIvannikov Institute for System Programming of the Russian Academy of SciencesТруды Института системного программирования РАН2079-81562220-64262018-10-01301254010.15514/ISPRAS-2018-30(1)-2451On the possibilities of FSM description of Parallel composition of Timed Finite State MachinesA. S. Tvardovskii0A. V. Laputenko1Национальный исследовательский Томский государственный университетНациональный исследовательский Томский государственный университет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.https://ispranproceedings.elpub.ru/jour/article/view/451конечный автоматвходные и выходные таймаутывременные ограничениякомпозиция |
| spellingShingle | A. S. Tvardovskii A. V. Laputenko On the possibilities of FSM description of Parallel composition of Timed Finite State Machines Труды Института системного программирования РАН конечный автомат входные и выходные таймауты временные ограничения композиция |
| title | On the possibilities of FSM description of Parallel composition of Timed Finite State Machines |
| title_full | On the possibilities of FSM description of Parallel composition of Timed Finite State Machines |
| title_fullStr | On the possibilities of FSM description of Parallel composition of Timed Finite State Machines |
| title_full_unstemmed | On the possibilities of FSM description of Parallel composition of Timed Finite State Machines |
| title_short | On the possibilities of FSM description of Parallel composition of Timed Finite State Machines |
| title_sort | on the possibilities of fsm description of parallel composition of timed finite state machines |
| topic | конечный автомат входные и выходные таймауты временные ограничения композиция |
| url | https://ispranproceedings.elpub.ru/jour/article/view/451 |
| work_keys_str_mv | AT astvardovskii onthepossibilitiesoffsmdescriptionofparallelcompositionoftimedfinitestatemachines AT avlaputenko onthepossibilitiesoffsmdescriptionofparallelcompositionoftimedfinitestatemachines |