Separating Input/Output Automata With Nondeterministic Behavior
https://doi.org/10.26907/1562-5419-2020-23-4-634-655
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.
About the Authors
I. B. Burdonov
Ivannikov Institute for System Programming of the Russian Academy of Sciences
Russian Federation
Russian Federation
N. V. Yevtushenko
Ivannikov Institute for System Programming of the Russian Academy of Sciences
Russian Federation
Russian Federation
A. S. Kossachev
Ivannikov Institute for System Programming of the Russian Academy of Sciences
Russian Federation
Russian Federation
References
1. Kam T., Villa T., Brayton K.R., Sangiovanni-Vincentelli A. Synthesis of FSMs: Functional Optimization. Springer. 1997. 282 p.
2. Бурдонов И.Б., Косачев А.С., Кулямин В.В. Теория соответствия для систем с блокировками и разрушением. Наука. Глав. ред. физ.-мат. лит., 2008. 412 c.
3. Tretmans J. A formal approach to conformance testing // The Intern. Workshop on Protocol Test Systems. 1993. P. 257–276.
4. Starke P. Abstract Automata. American Elsevier, 1972. 419 p.
5. Гилл А. Введение в теорию конечных автоматов. Наука, 1966. 272 с.
6. 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.
7. Евтушенко Н., Кушик Н. Некоторые задачи идентификации состояний для недетерминированных автоматов. СTT, 2018. 190 с.
8. Petrenko A., Yevtushenko N. Conformance Tests as Checking Experiments for Partial Nondeterministic FSM // Lecture Notes in Computer Science. 2005. V. 3997. P. 118–133.
9. Kushik N., Yevtushenko N., Burdonov I., Kossachev A. Synchronizing and Homing Experiments for Input/output Automata // System Informatics. 2017. No 10. P. 1–10.
Review
For citations:
Burdonov I.B., Yevtushenko N.V., Kossachev A.S. Separating Input/Output Automata With Nondeterministic Behavior. Russian Digital Libraries Journal. 2020;23(4):634-655. (In Russ.) https://doi.org/10.26907/1562-5419-2020-23-4-634-655
Views:
20
Email this article 