Preview

Труды Института системного программирования РАН

Расширенный поиск

Проверяющие эксперименты с ненаблюдаемым древовидными автоматами

https://doi.org/10.15514/ISPRAS-2015-27(6)-28

Аннотация

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

Об авторе

Н. Г. Кушик
Томский государственный университет; Телеком Южный Париж
Франция


Список литературы

1. M.П. Василевский. О распознавании неисправности автоматов. Кибернетика, № 4, 1973 г. стр. 98-108.

2. F. Hennie. Fault-Detecting Experiments for Sequential Circuits. Proc. Fifth Ann. Symp. Switching Circuit Theory and Logical Design, 1964. P. 95-110.

3. E. Moore. Gedanken-experiments on sequential machines Automata Studies, Annals of Mathematical Studies, No.1, 1956. P. 129-153.

4. D. Lee M. Yannakakis. Testing Finite-State Machines: State Identification and Verification. IEEE Transactions on Computers, 1994, Volume 43, Issue 3. P. 306-320.

5. S. Sandberg. Homing and Synchronization Sequences. Lecture Notes in Computer Science, № 3472, 2005. P. 5-33.

6. Н.В. Евтушенко, А.Ф. Петренко, М.В. Ветрова. Недетерминированные автоматы: анализ и синтез Ч. 1: Отношения и операции : учеб. пособие. Томск : Том. гос. ун-т, 2006. 142 с.

7. N. Spitsyna, K. El-Fakih, N. Yevtushenko. Studying the separability relation between finite state machines. Softw. Test., Verif. Reliab., 2007, Volume 17, Issue 4. P. 227-241.

8. N. Kushik, N. Yevtushenko, A. Cavalli. On Testing against Partial Non-observable Specifications. Proceedings of the 9th International Conference on the Quality of Information and Communications Technology, 2014. P. 230-233.


Рецензия

Для цитирования:


Кушик Н.Г. Проверяющие эксперименты с ненаблюдаемым древовидными автоматами. Труды Института системного программирования РАН. 2015;27(6):441-450. https://doi.org/10.15514/ISPRAS-2015-27(6)-28

For citation:


Kushik N. Checking experiments with non-observable tree FSMs. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2015;27(6):441-450. (In Russ.) https://doi.org/10.15514/ISPRAS-2015-27(6)-28



Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)