Разработка методов синтеза условных тестов для автоматных моделей с недетерминированным поведением тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат физико-математических наук Громов, Максим Леонидович

• Громов, Максим Леонидович
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Громов, Максим Леонидович

Введение

Принятые обозначения

1 Основные понятия и определения

1.1 Введение.

1.2 Входо-выходные полуавтоматы.

1.3 Автоматы.

1.4 Временные автоматы.

1.5 Краткий обзор литературы по синтезу условных тестов для автоматных моделей.

1.6 Выводы по главе 1.

2 Различающие эксперименты с недетерминированными автоматами

2.1 Введение.

2.2 Отношения r-совместимости и г-различимости.

2.3 Алгоритм построения r-различающего автомата.

2.4 Синтез проверяющих тестов при явно заданной области неисправности и по мутационному автомату.

2.5 Локализация неисправной компоненты в композиции двух конечных автоматов.

2.5.1 Модель неисправности и распознавание неисправной компоненты.

2.5.2 Параллельная композиция автоматов.

2.5.3 Модель неисправности и распознавание неисправной компоненты.

2.5.4 Результаты компьютерных экспериментов.

2.6 Основные результаты главы 2.

3 Различающие эксперименты с входо-выходными полуавтоматами

3.1 Введение.

3.2 Отношение ioeo-различимости.

3.3 Алгоритм построения ioco-различающего полуавтомата

3.4 Синтез проверяющих тестов на основе перебора элементов из области неисправности.

3.5 Связь между ioco и квази-редукцией.

3.5.1 Построение конечного автомата по входо-выходному полуавтомату.

3.5.2 Построение полного проверяющего теста для входо-выходных полуавтоматов на основе полного проверяющего теста для автоматов

3.6 Основные результаты главы 3.

4 Различающие эксперименты с временными автоматами

4.1 Введение.

4.2 Отношение г-совместимости.

4.3 Алгоритм построения r-различающего временного автомата

4.4 Синтез проверяющих тестов для явно заданной области неисправности

4.5 Основные результаты главы 4.

Введение диссертации (часть автореферата) на тему «Разработка методов синтеза условных тестов для автоматных моделей с недетерминированным поведением»

Актуальность проблемы. Тестирование является неотъемлемой частью жизненного цикла любой системы. Под тестированием понимается процесс подачи входных воздействий на тестируемую систему, наблюдение выходных реакций и вывод заключения о правильном или неправильном поведении системы [1-3]. Эмпирические тесты оказались недостаточными в первую очередь для систем управления сложными процессами, что, в свою очередь, привело к новому витку развития тестирования на основе формальных моделей. Для дискретных управляющих систем одной из широко используемых моделей при синтезе тестов является автоматная модель(см., например, [4-7]), и методы синтеза проверяющих тестов с гарантированной полнотой хорошо развиты для детерминированных автоматов [4,8-13]. Однако в ряде случаев поведение системы описывается недетерминированным автоматом [14-17]. Причины появления недетерминизма в спецификациях и реализациях, вообще говоря, различные [18,19]; среди них можно выделить возможность различных опций при реализации, уровень абстракции описания, невозможность полной управляемости и наблюдаемости для реализации и так далее. Одной из основных проблем при синтезе тестов для недетерминированных реализаций является тот факт, что в общем случае недетерминированный (проверяемый) автомат может реагировать различными выходными последовательностями на одну и ту же входную последовательность. Поэтому обычно при тестировании peaлизаций с недетерминированным поведением делается допущение о «всех погодных условиях» [20-22], то есть предполагается, что каждая тестовая входная последовательность подается на реализацию достаточно большое число раз в «различных погодных условиях», и поэтому можно считать, что тестер пронаблюдал все возможные выходные реакции реализации на каждую входную последовательность. Допущение о «всех погодных условиях» является скорее теоретическим, так как никто не знает, сколько раз достаточно подать входную последовательность, чтобы дать возможность тестеру «увидеть» все выходные реакции реализации. Более того, такому предположению невозможно удовлетворить, если проверяемый автомат является только частично контролируемым, что имеет место, например, при удаленном тестировании реализаций телекоммуникационных протоколов. В [23,24] предлагаются методы синтеза проверяющих тестов без использования предположения о «всех погодных условиях» при проведении безусловного эксперимента с проверяемой системой. Длины этих тестов большие, однако известно (см., например, [25-27]), что длина тестов может быть существенно сокращена на основе условного тестирования проверяемой системы. Таким образом, разработка методов синтеза условных проверяющих и диагностических тестов для систем с автоматным поведением без использования предположения о «всех погодных условиях» является актуальной задачей.

Цель работы. Разработка методов синтеза условных диагностических и проверяющих тестов для автоматных моделей с недетерминированным поведением, а именно для недетерминированных конечных автоматов, входо-выходных полуавтоматов и временных автоматов, которые в явном виде принимают во внимание временные аспекты системы.

Методы исследования. Для решения поставленных задач применяется аппарат дискретной математики, в частности, теории автоматов, математической логики, а также проводятся компьютерные эксперименты с целью исследования эффективности предлагаемых методов. Научная новизна.

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

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

3. Показано, что задачу построения конечного полного проверяющего теста относительно модели входо-выходного полуавтомата можно свести к задаче построения полного теста для недетерминированного автомата, и тем самым показано, что при построении конечного полного проверяющего теста для входо-выходных полуавтоматов можно использовать известные методы синтеза таких тестов для конечных автоматов.

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

Основные положения, выносимые на защиту.

1. Необходимые и достаточные условия распознавания двух недетерминированных автоматов посредством условного эксперимента и представление конечным автоматом условного эксперимента по распознаванию двух различимых автоматов.

2. Необходимые и достаточные условия распознавания двух входо-выходных полуавтоматов посредством условного эксперимента и представление конечным полуавтоматом условного эксперимента по распознаванию двух различимых полуавтоматов.

3. Метод построения полного проверяющего теста относительно модели входо-выходного полуавтомата на основе построения полного теста для соответствующего недетерминированного автомата, что позволяет строить конечные проверяющие тесты для входо-выходных полуавтоматов с гарантированной полнотой относительно ряда моделей неисправности.

4. Модель конечного временного автомата, являющаяся частным случаем расширенного временного автомата; понятие различимости для временных недетерминированных автоматов и критерий различимости двух недетерминированных временных автоматов условным экспериментом; представление условного эксперимента, различающего два временных автомата, в виде временного автомата.

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

Практическая ценность. Предложенные в работе методы и алгоритмы могут быть использованы в системах автоматизированного синтеза тестов для дискретных управляющих систем, в частности, в системах автоматического синтеза проверяющих и диагностических тестов для телекоммуникационных протоколов.

Реализация полученных результатов. Результаты диссертационной работы получены в рамках следующих проектов:

1. 6ая рамочная программа TAROT «Мобильность молодых учёных», 2003-2007 гг.

2. НИР «Разработка математических и программных средств обеспечения надёжного и безопасного доступа к электронным ресурсам коллективного пользования» (в рамках инновационного проекта ТГУ), 2006-2007 гг.

3. НИР «Проведение прикладных и проблемно-ориентированных поисковых исследований в области информационно-телекоммуникационных систем с участием научных организаций Франции» (шифр заявки «2009-04-1.4-00-02-003», госконтракт №02.514.12.4002 от 09.06.2009).

Апробация работы и публикации. Научные результаты, составившие основу данной работы, обсуждались на заседаниях объединенного научного семинара кафедры информационных технологий в исследовании дискретных структур радиофизического факультета ТГУ, кафедры программирования и кафедры защиты информации и криптографии факультета прикладной математики и кибернетики ТГУ.

Результаты работы докладывались на российских и международных конференциях: «East-West Design and Test Workshop» (Одесса, 2005 и Львов, 2008); IX Международном семинаре «Дискретная математика и её приложения» (Москва, 2007); Всероссийской конференции с международным участием «Новые информационные технологии в исследовании сложных структур» (Иркутск, 2004 и Шушенское, 2006); TESTCOM-2007 (Таллин, 2007); SYRCoSE (Санкт-Петербург, 2008, Москва, 2009).

По результатам проведенных исследований опубликовано 10 статей в научных журналах, докладов и тезисов докладов на конференциях различного уровня в том числе в пяти рецензируемых журналах:

1. Громов, М. К синтезу условных тестов для недетерминированных автоматов / М. Громов, Н. Евтушенко, А. Коломеец // Программирование. — 2008. — №6. — С. 1—11.

2. Громов, M.JI. Синтез диагностических тестов для автоматных сетей / M.JI. Громов, А.В. Коломеец, Н.В. Евтушенко // Вестник ТГУ. Приложение. - 2004. - №9(1). - С. 204-209.

3. Gromov, М. Testing and Model-Checking Techniques for Diagnosis / M. Gromov and T. Willemse // Vol.4581 of LNCS. - Springer, 2007. - Pp.138-154.

4. Громов, M.JI. О распознавании недетерминированного автомата в заданном классе / M.JI. Громов, Н.В. Шабалдина // Материалы IX Международного семинара «Дискретная математика и её приложения» / Под ред. О.М. Касим-Заде. - М.: ММФ МГУ, 2007. - С. 157-160.

5. Громов, М. Метод построения полного проверяющего теста для входо-выходных полуавтоматов / М. Громов // Вестник ТГУ. Управление, вычислительная техника и информатика. — 2008. — №3(4). — С. 85-98.

6. Gromov, M.L. On the synthesis of adaptive tests for nondeterministic finite state machines / M.L. Gromov, N.V. Evtushenko, A.V. Kolomeets // Program. Comput. Softw. - 2008. - Vol. 34, no. 6. - Pp. 322-329.

7. Громов, M. Об одном классе автоматов с полиномиальной оценкой числа состояний в наблюдаемой форме / М. Громов, О. Кондратьева Журнал СФУ. Серия: Математика и физика — 2008. — Т.1, №3. -С. 257-261.

8. Gromov, М. A novel method for derivation of a test with guaranteed coverage for LTS / M. Gromov // Proceedings of SYRCoSE 2008. -St.Peterburg:S-PSU, 2008. - Pp. 47-49.

9. Gromov, M. Deriving test suites for timed Finite State Machines / M. Gromov, D. Popov, N. Yevtushenko // Proceedings of IEEE East-West Design & Test Symposium'08. — Kharkov, Ukraine: SPD FL Stepanov V.V., 2008. - Pp. 339-343.

10. Distinguing Non-deterministic Timed Finite State Machines / M. Gromov, K. El-Fakih, N. Shabaldina, N. Yevtushenko // Vol. 5522 of LNCS. - Springer, 2009. - Pp. 137-151.

Структура и объём работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы; изложена на 152 страницах, включая 7 рисунков и список литературы из 77 наименований. Во введении дается общая характеристика работы, обосновывается актуальность исследований, определяется тематика и формулируется цель работы, кратко излагаются основные задачи и результаты, выносимые на защиту.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Громов, Максим Леонидович

4.5. Основные результаты главы 4

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

Заключение

В заключение перечислим ещё раз основные результаты, полученные в диссертационной работе.

1. Введено понятие r-различимости двух автоматов. Установлены необходимые и достаточные условия различимости двух автоматов условным экспериментом. Показано, что два автомата различимы условным экспериментом, если и только если эти автоматы г-различимы, то есть если и только если для них существует r-различающий автомат.

2. На основе пересечения двух автоматов предложен алгоритм построения r-различающего автомата для двух автоматов. Введено понятие тестового примера для автоматной модели неисправности, как r-различающего автомата специального вида. Предложен метод построения конечных проверяющих тестов для автоматной модели неисправности в случае, когда область неисправности перечислена явно. Показано, когда такие тесты будут полными. Предложен алгоритм сокращения перебора автоматов при построении проверяющего теста для случая, когда область неисправности является множеством всех полностью определённых подавтоматов мутационного автомата.

3. Введено понятие ioсо-различимости двух входо-выходных полуавтоматов. Установлены необходимые и достаточные условия различимости двух входо-выходных полуавтоматов условным экспериментом. Показано, что два входо-выходных полуавтомата различимы условным экспериментом, если и только если эти полуавтоматы ioco-различимы, то есть если и только если для них существует ioco-различающий полуавтомат.

4. На основе пересечения входо-выходных полуавтоматов предложен алгоритм построения 1осо-различающего полуавтомата для двух полуавтоматов. Введено понятие тестового примера для полуавтоматной модели неисправности как ioco-различающего входо-выходного полуавтомата специального вида. Предложен метод построения конечных проверяющих тестов для полуавтоматной модели неисправности в случае, когда область неисправности перечислена явно. Показано, когда такие тесты будут полными.

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

6. Введено понятие временного автомата для описания поведения систем с явно заданными временными аспектами поведения; введено понятие пересечения двух наблюдаемых временных автоматов, которое описывает общую часть их поведения.

7. Введено понятие r-различимости двух временных автоматов. Установлены необходимые и достаточные условия различимости двух временных автоматов условным экспериментом. Показано, что два временных автомата различимы условным экспериментом, если и только если эти временные автоматы r-различимы, то есть если и только если для них существует r-различающий временной автомат.

8. На основе пересечения временных автоматов предложен алгоритм построения r-различающего временного автомата для двух автоматов. Введено понятие тестового примера для модели неисправности с временными автоматами как r-различающего временного автомата специального вида. Предложен метод построения конечных проверяющих тестов для модели неисправности с временными автоматами в случае, когда область неисправности перечислена явно. Показано, когда такие тесты будут полными.

Алгоритмы и их программные реализации, разработанные в процессе выполнения диссертационной работы, могут быть использованы в системах автоматического синтеза проверяющих и диагностических тестов для систем логического управления, в частности, в системах автоматического синтеза проверяющих и диагностических тестов для протоколов телекоммуникационных систем.

Список литературы диссертационного исследования кандидат физико-математических наук Громов, Максим Леонидович, 2009 год

1. Gill, A. 1.troduction to the theory of Finite-State Machines / A. Gill. — McGraw-Hill, 1962.

2. Moore, E. F. Gedanken-Experiments on Sequential Machines / E. F. Moore; Ed. by C. Shannon, J. McCarthy. — Princeton, New Jersey: Princeton University Press, 1956.— Pp. 129-153.

3. Основы технической диагностики / П. Пархоменко, В. Карибский, Е. Согомонян, В. Халчев. — Энергоиздат, 1976. — 464 с.

4. Chow, Т. S. Testing software design modeled by finite-state machines / T. S. Chow // IEEE Trans. Softw. Eng. ~ 1978. Vol. 4, no. 3. - Pp. 178187.

5. Conformance testing of protocols specified as communicating finitestate machines a guided random walk based approach / D. Lee, К. K. Sab-nani, D. M. Kristol, S. Paul // IEEE Transactions on Communications. — 1996. - Vol. 44, no. 5. - Pp. 631-640.

6. Lai, R. A survey of communication protocol testing / R. Lai j j J. Syst. Softw. 2002. — Vol. 62, no. 1. - Pp. 21-46.

7. Hennie, F. C. Fault detecting experiments for sequential circuits / F. C. Hennie // Proc. of 5th Annual Symposium on Switching Circuit Theory and Logical Design. — Princeton, USA: Princeton University Press, 1964.-Pp. 95-110.

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

9. Yannakakis, М. Testing finite state machines: fault detection / M. Yan-nakakis, D. Lee j j Selected papers of the 23rd annual ACM symposium on Theory of computing. — Orlando, FL, USA: Academic Press, Inc., 1995. — Pp. 209-227.

10. Lee, D. Principles and methods of testing finite state machines a survey / D. Lee, M. Yannakakis // Proceedings of the IEEE.- 1996.- Vol. 84, no. 8.-Pp. 1090-1123.

11. Petrenko, A. Testing from partial deterministic fsm specifications / A. Pe-trenko, N. Yevtushenko // IEEE Trans. Comput2005.- Vol. 54, no. 9,- Pp. 1154-1165.

12. Dorofeeva, R. An improved conformance testing method / R. Dorofeeva, K. El-Fakih, N. Yevtushenko // Formal Techniques for Networked and Distributed Systems FORTE 2005. - LNCS. - Berlin, Heidelberg: Springer, 2005. - Pp. 204-218.

13. Hierons, R. M. Adaptive testing of a deterministic implementation against a nondeterministic finite state machine / R. M. Hierons // The Computer Journal. 1998. - Vol. 41, no. 5. - Pp. 349-355.

14. Hierons, R. M. Generating candidates when testing a deterministic implementation against a non-deterministic finite-state machine / R. M. Hierons // The Computer Journal. 2003. - Vol. 46, no. 3. - Pp. 307-318.

15. Hierons, R. M. Testing from a nondeterministic finite state machine using adaptive state counting / R. M. Hierons // IEEE Trans. Comput. — 2004. — Vol. 53, no. 10. Pp. 1330-1342.

16. Coping with nondeterminism in network protocol testing / R. Miller, D.-L. Chen, D. Lee, R. Hao // Testing of Communicating Systems. — Vol. 3502 of LNCS. Berlin, Heidelberg: Springer, 2005. - Pp. 129-145.

17. Milner, R. Communication and concurrency / R. Milner. — Upper Saddle River, NJ, USA: Prentice-Hall, Inc., 1989.

18. Luo, G. Test selection based on communicating nondeterministic finite-state machines using a generalized wp-method / G. Luo, G. von Bochmann, A. Petrenko // IEEE Trans. Softw. Eng.— 1994.- Vol. 20, no. 2.— Pp. 149-162.

19. Selecting test sequences for partially-specified nondeterministic finite state machines / G. Luo, A. Petrenko, R. Petrenko, G. V. Bochmann //In IFIP 7th International Workshop on Protocol Test Systems. — 1994.— Pp. 91106.

20. Spitsyna, N. Studying the separability relation between finite state machines / N. Spitsyna, K. El-Fakih, N. Yevtushenko // Softw. Test. Verif. Reliab. 2007. - Vol. 17, no. 4. - Pp. 227-241.

21. Hierons, R. M. Concerning the ordering of adaptive test sequences /

22. R. M. Hierons, H. Ural // Formal Techniques for Networked and Distributed Systems FORTE 2003. - Vol. 2767 of LNCS. - Berlin, Heidelberg: Springer, 2003. - Pp. 289-302.

23. Hierons, R. M. Reducing the cost of applying adaptive test cases / R. M. Hierons, H. Ural // Comput. Netw. — 2007. — Vol. 51, no. 1.- Pp. 224-238.

24. Tretmans, J. Test generation with inputs, outputs and repetitive quiescence / J. Tretmans // Software—Concepts and Tools. — 1996.— Vol. 17, no. 3.-Pp. 103-120.

25. Бурдонов, И. Б. Теория конформности для функционального тестирования программных систем на основе формальных моделей: автореф. диссертации на соискание степени д-ра физ-мат. наук: 05.13.11.— М., 2008. 60 с.

26. Merayo, М. G. Extending efsms to specify and test timed systems with action durations and time-outs. / M. G. Merayo, M. Nunez, I. Rodriguez // IEEE Transactions on Computers. 2008. - Vol. 57, no. 6. - Pp. 835-844.

27. Трахтенброт, Б. А. Конечные автоматы. Поведение и синтез / Б. А. Трахтенброт, Я. М. Барздинь.— М.: Наука, 1970.

28. Громов, М. Л. Об одном классе автоматов с полиномиальной оценкой числа состояний в наблюдаемой форме / М. JI. Громов, О. В. Кондратьева // Журнал Сибирского федерального университета. Серия: Математика и физика. — 2008. — Т. 1, № 3. — С. 257-261.

29. Formal test automation: A simple experiment / A. Belinfante, J. Feenstra, R. G. d. Vries et al. // Proceedings of the IFIP TC6 12th International

30. Workshop on Testing Communicating Systems. — Deventer, The Netherlands: Kluwer, B.V., 1999,- Pp. 179-196.

31. Vries, R. G. d. Towards formal test purposes / R. G. d. Vries, J. Tret-mans // Proceedings of the Workshop on Formal Approaches to Testing of Software / Ed. by E. Brinksma, J. Tretmans. — Vol. NS-01-04. — Aarhus: 2001.-Pp. 61-76.

32. Starke, P. H. Abstract Automata / P. H. Starke.— Elsevier, 1972.— 419 pp.

33. Куфарева, И. Б. Применение недетерминированных автоматов в задачах синтеза проверяющих тестов для систем логического управления: диссертация на соискание степени к-та. тех. наук: 05.13.01.— Томск: ТГУ, 2000.- 176 с.

34. Merayo, М. G. Formal testing from timed finite state machines / M. G. Merayo, M. Nunez, I. Rodriguez // Computer Networks. — 2008.— Vol. 52, no. 2.- Pp. 432-460.

35. Gaston, С. Unitary testing of components in context / C. Gaston, P. Le Gall. Invited lecture at 5th TAROT Summer School 2009, Spain.

36. Petrenko, A. Fault model-driven test derivation from finite state models: annotated bibliography / A. Petrenko. 2001. — Pp. 196-205.

37. Hierons, R. M. Testing in the distributed test architecture: An extended abstract / R. M. Hierons // Quality Software, International Conference on. 2008. - Vol. 0. - Pp. 11-14.

38. Hierons, R. M. The effect of the distributed test architecture on the power of testing / R. M. Hierons, H. Ural // Comput. J.— 2008.- Vol. 51, no. 4.- Pp. 497-510.

39. Hierons, R. Checking sequences for distributed test architectures / R. Hierons, H. Ural // Distributed Computing. — 2008. — September. — Vol. 21, no. 3. — Pp. 223-238. http://dx.doi.org/10.1007/s00446-008-0062-4.

40. Hierons, R. M. Overcoming controllability problems with fewest channels between testers / R. M. Hierons, H. Ural j j Comput. Netw. — 2009. — Vol. 53, no. 5. Pp. 680-690.

41. Hierons, R. M. Testing distributed systems / R. M. Hierons. — Invited lecture at 5th TAROT Summer School 2009, Spain.

42. Petrenko, A. Conformance tests as checking experiments for partial non-deterministic fsm / A. Petrenko, N. Yevtushenko // Formal Approaches to Software Testing. — Vol. 3997 of LNCS. ~ Berlin, Heidelberg: Springer, 2006.-Pp. 118-133.

43. Tretmans, J. Model based testing with labelled transition systems / J. Tret-mans // Formal Methods and Testing. — 2008. — Pp. 1-38.

44. G. v. Bochmann, A. Petrenko, M. Yao 11IWPTS '94: 7th IFIP WG 6.1 international workshop on Protocol test systems. — London, UK, UK: Chapman к Hall, Ltd., 1995,- Pp. 55-76.

45. Glabbeek, R. J. v. The linear time-branching time spectrum (extended abstract) / R. J. v. Glabbeek // CONCUR '90: Proceedings of the Theories of Concurrency: Unification and Extension. — London, UK: Springer-Verlag, 1990.- Pp. 278-297.

46. Vaandrager, F. W. On the relationship between process algebra and input/output automata (extended abstract) / F. W. Vaandrager //In Proceedings 6 th Annual Symposium on Logic in Computer Science. — IEEE Computer Society Press, 1991.- Pp. 387-398.

47. Tan, Q. M. Test generation for specifications modeled by input/outputautomata / Q. M. Tan, A. Petrenko // IWTCS: Proceedings of the IFIPf

48. TC6 11th International Workshop on Testing Communicating Systems. — Deventer, The Netherlands: Kluwer, B.V., 1998,- Pp. 83-100.

49. Alur, R. A theory of timed automata / R. Alur, D. L. Dill // Theor. Comput. Sci. — 1994. — Vol. 126, no. 2.- Pp. 183-235.

50. Springintveld, J. Testing timed automata / J. Springintveld, F. Vaandrager,

51. P. R. D'Argenio // Theor. Comput. Scz. 2001. - Vol. 254, no. 1-2.-Pp. 225-257.

52. En-Nouaary, A. Timed wp-method: Testing real-time systems / A. En-Nouaary, R. Dssouli, F. Khendek // IEEE Trans. Softw. Eng. 2002. -Vol. 28, no. 11. - Pp. 1023-1038.

53. Tripakis, S. Folk theorems on the determinization and minimization of timed automata / S. Tripakis // Inf. Process. Lett. — 2006. — Vol. 99, no. 6.- Pp. 222-226.

54. Hierons, R. M. Testing from a stochastic timed system with a fault model / R. M. Hierons, M. G. Merayo, M. Nunez // Journal of Logic and Algebraic Programming. 2008. — Vol. 78, no. 2. — Pp. 98-115.

55. El-Fakih, K. Testing Timed Finite State Machines with guaranteed fault coverage / K. El-Fakih, N. Yevtushenko, H. Fouchal. — Принята к публикации на TESTCOM-2009.

56. Громов, М. К синтезу условных тестов для недетерминированных автоматов / М. Громов, Н. Евтушенко, А. Коломеец // Программирование. 2008. - № 6. - С. 1-11.

57. Громов, М. Л. О распознавании недетерминированного автомата в заданном классе / М. JI. Громов, Н. В. Шабалдина // Материалы IX Международного семинара «Дискретная математика и её приложения» / Под ред. О. М. Касим-Заде,- М.: ММФ МГУ, 2007.- С. 157160.

58. Громов, М. Л. Синтез диагностических тестов для автоматных сетей / М. JT. Громов, А. В. Коломеец, Н. В. Евтушенко // Вестник ТГУ. Приложение. 2004. - № 9(1). - С. 204-209.

59. Gromov, М. L. On the synthesis of adaptive tests for nondeterministic finite state machines / M. L. Gromov, N. V. Evtushenko, A. V. Kolomeets // Program. Comput. Softw. 2008. - Vol. 34, no. 6. - Pp. 322-329.

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

61. El-Fakih, K. Fsm-based re-testing methods / K. El-Fakih, N. Yevtushenko,

62. G. v. Bochmann // TestCom '02: Proceedings of the IFIP 14th International Conference on Testing Communicating Systems XIV. — Deventer, The Netherlands, The Netherlands: Kluwer, B.V., 2002. Pp. 373-390.

63. Fault diagnosis in extended finite state machines / K. El-Fakih, S. Prokopenko, N. Yevtushenko, G. von Bochmann // Proc. of the IFIP 15th International Conference, TesCom'03 / Ed. by H. Dieter, A. Wiles. — LNCS. Berlin: Springer, 2003.- Pp. 197-210.

64. Громов, M. Метод построения полного проверяющего теста для входо-выходных полуавтоматов / М. Громов // Вестник ТГУ. Управление, вычислительная техника и информатика. — 2008. — № 3(4). — С. 8598.

65. Gromov, М. A novel method for derivation of a test with guaranteed coverage for Its / M. Gromov // Proceedings of SYRCoSE 2008. St. Peterburg: S-PSU, 2008. - Pp. 47-49.

66. Gromov, M. Deriving test suites for timed finite state machines / M. Gromov, D. Popov, N. Yevtushenko // Proceedings of IEEE East-West Design & Test Symposium'08. — Kharkov, Ukraine: SPD FL Stepanov V.V., 2008. Pp. 339-343.