Separating Input/Output Automata With Nondeterministic Behavior

Main Article Content

Igor Borisovich Burdonov
Nina Vladimirovna Yevtushenko
Alexander Sergeevich Kossachev

Abstract

When deriving tests for checking functional and nonfunctional requirements for components of control systems, the notion of separablity becomes very important that is used for distinguishing the fault-free component from a faulty one. In order to do this, proper separating sequences are utilized. Such sequences are well studied for complete and deterministic Finite State Machines but components of control systems can be only partially described and their behavior can be nondeterministic. In this paper, we consider the formal model of Input/Output automata, introduce the notion of a separating sequence for two such automata and propose an approach for deriving such a separating sequence.

Article Details

Author Biographies

Igor Borisovich Burdonov

Leading Researcher, Ivannikov Institute for System Programming of the RAS. Research interests - modeling and verification of software systems, graph theory, automata.

Nina Vladimirovna Yevtushenko

Leading researcher of Ivannikov Institute for System Programming of the RAS. Research interests – automata theory, modeling, verification and testing of software systems, telecommunication protocols and services.

Alexander Sergeevich Kossachev

Leading Researcher, Ivannikov Institute for System Programming of the RAS. Research interests - modeling and verification of software systems, graph theory, automata.

References

Kam T., Villa T., Brayton K.R., Sangiovanni-Vincentelli A. Synthesis of FSMs: Functional Optimization. Springer. 1997. 282 p.

Бурдонов И.Б., Косачев А.С., Кулямин В.В. Теория соответствия для систем с блокировками и разрушением. Наука. Глав. ред. физ.-мат. лит., 2008. 412 c.

Tretmans J. A formal approach to conformance testing // The Intern. Workshop on Protocol Test Systems. 1993. P. 257–276.

Starke P. Abstract Automata. American Elsevier, 1972. 419 p.

Гилл А. Введение в теорию конечных автоматов. Наука, 1966. 272 с.

Kushik N., Yevtushenko N., Cavalli A.R. On Testing against partial nondeterministic machines // Intern. Conf. on the Quality of information and Communications Technology. 2014. P. 230–233.

Евтушенко Н., Кушик Н. Некоторые задачи идентификации состояний для недетерминированных автоматов. СTT, 2018. 190 с.

Petrenko A., Yevtushenko N. Conformance Tests as Checking Experiments for Partial Nondeterministic FSM // Lecture Notes in Computer Science. 2005. V. 3997. P. 118–133.

Kushik N., Yevtushenko N., Burdonov I., Kossachev A. Synchronizing and Homing Experiments for Input/output Automata // System Informatics. 2017. No 10. P. 1–10.