maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2017-6-730-742mais-610Research ArticleОригинальные статьиArticlesК синтезу синхронизирующих и установочных последовательностей для входо-выходных полуавтоматовDeriving Synchronizing and Homing Sequences for Input/Output AutomataКушикНаталья ГеннадьевнаKushikNatalia G.

д-р физ.-мат. наук

PhD, Assistant Professor

natalia.kushik@telecom-sudparis.euhttps://orcid.org/0000-0002-4006-1161ЕвтушенкоНина ВладимировнаYevtushenkoNina V.

д-р техн. наук, профессор

PhD, Professor

nyevtush@gmail.comhttps://orcid.org/0000-0001-9539-7853БурдоновИгорь БорисовичBurdonovIgor B.

д-р физ.-мат. наук, старший научный сотрудник

PhD, Senior Researcher

igor@ispras.ruhttps://orcid.org/0000-0001-5316-3813КосачевАлександр СергеевичKossatchevAlexander S.

канд. физ.-мат. наук, старший научный сотрудник

PhD, Senior Researcher

kos@ispras.ruУниверситет Телеком Южный ПарижФранцияT´el´ecom SudParis/Universit´e Paris-SaclayFranceИнститут системного программирования РАН; Томский государственный университетРоссияInstitute for System Programming RAS; Tomsk State UniveristyRussian FederationИнститут системного программирования РАНРоссияInstitute for System Programming RASRussian Federation201718122017246730742Copyright © Кушик Н.Г., Евтушенко Н.В., Бурдонов И.Б., Косачев А.С., 20172017Кушик Н.Г., Евтушенко Н.В., Бурдонов И.Б., Косачев А.С.Kushik N.G., Yevtushenko N.V., Burdonov I.B., Kossatchev A.S.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/610

В работе рассматриваются задачи проверки существования и синтеза синхронизирующих и установочных последовательностей для конечных входо-выходных полуавтоматов. Соответствующие последовательности могут быть использованы при идентификации состояния проверяемой системы после подачи подходящей входной последовательности. В модели, исследуемой в работе, действия разделены на входные и выходные, однако отсутствуют выделенные явно семейства начальных и финальных состояний. В статье определяются понятия синхронизирующей и установочной последовательностей и предлагаются методы их синтеза для специального класса входо-выходных полуавтоматов, у которых в каждом состоянии определены переходы или только по входным, или только по выходным действиям; кроме того, в соответствующем графе переходов отсутствуют циклы по выходным символам. Для описанного класса входо-выходных полуавтоматов устанавливаются необходимые и достаточные условия существования синхронизирующих и установочных последовательностей и оценивается длина таких последовательностей. Выделяются подклассы полуавтоматов, для которых худшие (в основном экспоненциальные) оценки сложности не являются достижимыми.

 

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.

 

входо-выходные полуавтоматысинхронизирующая последовательностьустановочная последовательностьinput/output automatasynchronizing sequencehoming sequenceReferencesМартюгин П. В., “Нижние оценки длины кратчайших бережно синхронизирующих слов для двух- и трёхбуквенных частичных автоматов”, Дискретн. анализ и исслед. опер., 15:4 (2008), 44–56;Martjugin P. V., “Nizhnie ocenki dliny kratchajshih berezhno sinhronizirujushhih slov dlja dvuh- i trjohbukvennyh chastichnyh avtomatov”, Diskretn. analiz i issled. oper., 15:4 (2008), 44–56, (in Russian).Gill A., “State-identification experiments in finite automata”, Information and Control, 4 (1961), 132–154.Gill A., “State-identification experiments in finite automata”, Information and Control, 4 (1961), 132–154.Martyugin P., “Computational Complexity of Certain Problems Related to Carefully Synchronizing Words for Partial Automata and Directing Words for Nondeterministic Automata”, Theory Comput. Syst., 54:2 (2014), 293–304.Martyugin P., “Computational Complexity of Certain Problems Related to Carefully Synchronizing Words for Partial Automata and Directing Words for Nondeterministic Automata”, Theory Comput. Syst., 54:2 (2014), 293–304.Hierons R. M., Jourdan G. V., Ural H., Yenig¨un H., “Using adaptive distinguishing sequences in checking sequence constructions”, Proc. of the 2008 ACM symposium on Applied computing (SAC), ACM, 2008, 682–687.Hierons R. M., Jourdan G. V., Ural H., Yenig¨un H., “Using adaptive distinguishing sequences in checking sequence constructions”, Proc. of the 2008 ACM symposium on Applied computing (SAC), ACM, 2008, 682–687.Ito M., Shikishima-Tsuji K., “Some Results on Directable Automata”, Theory Is Forever: Essays Dedicated to Arto Salomaa on the Occasion of His 70th Birthday, Lecture Notes in Computer Science, 3113, Springer, Berlin, Heidelberg, 2004, 125–133.Ito M., Shikishima-Tsuji K., “Some Results on Directable Automata”, Theory Is Forever: Essays Dedicated to Arto Salomaa on the Occasion of His 70th Birthday, Lecture Notes in Computer Science, 3113, Springer, Berlin, Heidelberg, 2004, 125–133.Kohavi Z., Switching and Finite Automata Theory, McGraw-Hill, New York, 1978.Kohavi Z., Switching and Finite Automata Theory, McGraw-Hill, New York, 1978.Kushik N., El-Fakih K., Yevtushenko N., Cavalli A.R., “On adaptive experiments for nondeterministic finite state machines”, International Journal on Software Tools for Technology Transfer, 18:3 (2016), 251–264.Kushik N., El-Fakih K., Yevtushenko N., Cavalli A.R., “On adaptive experiments for nondeterministic finite state machines”, International Journal on Software Tools for Technology Transfer, 18:3 (2016), 251–264.Kushik N., L´opez J., Cavalli A.R., Yevtushenko N., “Improving Protocol Passive Testing through ’Gedanken’ Experiments with Finite State Machines”, Proc. 2016 IEEE International Conference on Software Quality, Reliability and Security (QRS), IEEE, 2016, 315–322.Kushik N., L´opez J., Cavalli A.R., Yevtushenko N., “Improving Protocol Passive Testing through ’Gedanken’ Experiments with Finite State Machines”, Proc. 2016 IEEE International Conference on Software Quality, Reliability and Security (QRS), IEEE, 2016, 315–322.Kushik N., El-Fakih K., Yevtushenko N., “Preset and adaptive homing experiments for nondeterministic finite state machines”, Implementation and Application of Automata. CIAA 2011, Lecture Notes in Computer Science, 6807, 2011, 215–224.Kushik N., El-Fakih K., Yevtushenko N., “Preset and adaptive homing experiments for nondeterministic finite state machines”, Implementation and Application of Automata. CIAA 2011, Lecture Notes in Computer Science, 6807, 2011, 215–224.Kushik N., Yevtushenko N., “On the Length of Homing Sequences for Nondeterministic Finite State Machines”, Implementation and Application of Automata. CIAA 2013, Lecture Notes in Computer Science, 7982, 2013, 220–231.Kushik N., Yevtushenko N., “On the Length of Homing Sequences for Nondeterministic Finite State Machines”, Implementation and Application of Automata. CIAA 2013, Lecture Notes in Computer Science, 7982, 2013, 220–231.Lee D., Yannakakis M., “Testing finite-state machines: state identification and verification”, IEEE Trans. on Computers., 43:3 (1994), 306–320.Lee D., Yannakakis M., “Testing finite-state machines: state identification and verification”, IEEE Trans. on Computers., 43:3 (1994), 306–320.Moore E.F., “Gedanken-experiments on sequential machines”, Automata Studies (Annals of Mathematical Studies), Princeton University Press, 1956, 129–153.Moore E.F., “Gedanken-experiments on sequential machines”, Automata Studies (Annals of Mathematical Studies), Princeton University Press, 1956, 129–153.Sandberg S., “Homing and Synchronizing Sequences”, Model-Based Testing of Reactive Systems, Lecture Notes in Computer Science, 3472, 2005, 5–33.Sandberg S., “Homing and Synchronizing Sequences”, Model-Based Testing of Reactive Systems, Lecture Notes in Computer Science, 3472, 2005, 5–33.Tretmans J., “Test Generation with Inputs, Outputs and Repetitive Quiescence”, Software – Concepts and Tools, 17:3 (1996), 103–120.Tretmans J., “Test Generation with Inputs, Outputs and Repetitive Quiescence”, Software – Concepts and Tools, 17:3 (1996), 103–120.Volkov M.V., “Synchronizing Automata and the Cern´y Conjecture”, ˇ Language and Automata Theory and Applications. LATA 2008, Lecture Notes in Computer Science, 5196, 11–27.Volkov M.V., “Synchronizing Automata and the Cern´y Conjecture”, ˇ Language and Automata Theory and Applications. LATA 2008, Lecture Notes in Computer Science, 5196, 11–27.Kushik N.G, Yevtushenko N.V, Burdonov I.B., Kossatchev A.S, “Synchronizing and Homing Experiments for Input/output Automata”, System Informatics, 2017, № 10, 1–9.Kushik N.G, Yevtushenko N.V, Burdonov I.B., Kossatchev A.S, “Synchronizing and Homing Experiments for Input/output Automata”, System Informatics, 2017, № 10, 1–9.Yenig¨un H., Yevtushenko N., Kushik N., “The complexity of checking the existence and derivation of adaptive synchronizing experiments for deterministic FSMs”, Information Processing Letters, 127 (2017), 49–53.Yenig¨un H., Yevtushenko N., Kushik N., “The complexity of checking the existence and derivation of adaptive synchronizing experiments for deterministic FSMs”, Information Processing Letters, 127 (2017), 49–53.

The authors declare that there are no conflicts of interest present.