Deriving Synchronizing and Homing Sequences for Input/Output Automata
In this paper, we study the problem of existence check and derivation of synchronizing and homing sequences for finite input/output automata. Corresponding sequences can be effectively used for the current state identification of a system under test / verification, after the input sequence is applie...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2017-12-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/610 |
| _version_ | 1826559092721713152 |
|---|---|
| author | Natalia G. Kushik Nina V. Yevtushenko Igor B. Burdonov Alexander S. Kossatchev |
| author_facet | Natalia G. Kushik Nina V. Yevtushenko Igor B. Burdonov Alexander S. Kossatchev |
| author_sort | Natalia G. Kushik |
| collection | DOAJ |
| description | In this paper, we study the problem of existence check and derivation of synchronizing and homing sequences for finite input/output automata. Corresponding sequences can be effectively used for the current state identification of a system under test / verification, after the input sequence is applied. In the model considered in the paper, the alphabet of actions is divided into disjoint sets of inputs and outputs; however, no sets of possible initial or final states are defined. We introduce the notions of homing and synchronizing sequences for a specific class of such machines for which at each state the transitions only under inputs or under outputs are defined, and the machine transition diagram does not contain cycles labeled by outputs, i.e. the language of the machine does not contain traces with infinite postfix of outputs. For such a class of input/output automata, we establish necessary and sufficient conditions for the existence of synchronizing and homing sequences and discuss the length of such sequences. We also define some subclasses of automata for which the worst-case upper bounds (normally, exponential) are not reachable. |
| first_indexed | 2024-04-10T02:26:07Z |
| format | Article |
| id | doaj.art-792e93e4dd5a4eada802e092e65a3514 |
| institution | Directory Open Access Journal |
| issn | 1818-1015 2313-5417 |
| language | English |
| last_indexed | 2025-03-14T08:54:54Z |
| publishDate | 2017-12-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj.art-792e93e4dd5a4eada802e092e65a35142025-03-02T12:46:51ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172017-12-0124673074210.18255/1818-1015-2017-6-730-742444Deriving Synchronizing and Homing Sequences for Input/Output AutomataNatalia G. Kushik0Nina V. Yevtushenko1Igor B. Burdonov2Alexander S. Kossatchev3T´el´ecom SudParis/Universit´e Paris-SaclayInstitute for System Programming RAS; Tomsk State UniveristyInstitute for System Programming RASInstitute for System Programming RASIn this paper, we study the problem of existence check and derivation of synchronizing and homing sequences for finite input/output automata. Corresponding sequences can be effectively used for the current state identification of a system under test / verification, after the input sequence is applied. In the model considered in the paper, the alphabet of actions is divided into disjoint sets of inputs and outputs; however, no sets of possible initial or final states are defined. We introduce the notions of homing and synchronizing sequences for a specific class of such machines for which at each state the transitions only under inputs or under outputs are defined, and the machine transition diagram does not contain cycles labeled by outputs, i.e. the language of the machine does not contain traces with infinite postfix of outputs. For such a class of input/output automata, we establish necessary and sufficient conditions for the existence of synchronizing and homing sequences and discuss the length of such sequences. We also define some subclasses of automata for which the worst-case upper bounds (normally, exponential) are not reachable.https://www.mais-journal.ru/jour/article/view/610input/output automatasynchronizing sequencehoming sequence |
| spellingShingle | Natalia G. Kushik Nina V. Yevtushenko Igor B. Burdonov Alexander S. Kossatchev Deriving Synchronizing and Homing Sequences for Input/Output Automata Моделирование и анализ информационных систем input/output automata synchronizing sequence homing sequence |
| title | Deriving Synchronizing and Homing Sequences for Input/Output Automata |
| title_full | Deriving Synchronizing and Homing Sequences for Input/Output Automata |
| title_fullStr | Deriving Synchronizing and Homing Sequences for Input/Output Automata |
| title_full_unstemmed | Deriving Synchronizing and Homing Sequences for Input/Output Automata |
| title_short | Deriving Synchronizing and Homing Sequences for Input/Output Automata |
| title_sort | deriving synchronizing and homing sequences for input output automata |
| topic | input/output automata synchronizing sequence homing sequence |
| url | https://www.mais-journal.ru/jour/article/view/610 |
| work_keys_str_mv | AT nataliagkushik derivingsynchronizingandhomingsequencesforinputoutputautomata AT ninavyevtushenko derivingsynchronizingandhomingsequencesforinputoutputautomata AT igorbburdonov derivingsynchronizingandhomingsequencesforinputoutputautomata AT alexanderskossatchev derivingsynchronizingandhomingsequencesforinputoutputautomata |