RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Труды ИСП РАН:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Труды ИСП РАН, 2016, том 28, выпуск 1, страницы 151–184 (Mi tisp9)  

Система автоматов: условия детерминизма и тестирование

И. Б. Бурдонов, А. С. Косачев

Институт системного программирования РАН, 109004, Россия, г. Москва, ул. А. Солженицына, д. 25

Аннотация: Статья посвящена проблеме тестирования составных систем, компоненты которых моделируются конечными автоматами с несколькими входами и выходами, а взаимодействие между ними — обменом сообщениями по симплексным каналам связи. Система описывается ориентированным графом связей, вершина которого соответствует автомату компонента, а дуга — каналу связи, соединяющему выход одного автомата со входом другого автомата. Предполагается выполненной следующая гипотеза о связях: граф связей статический, а отображаемая им структура связей не содержит ошибок. Автомат, находящийся в вершине графа, в каждом состоянии может принимать несколько сообщений по своим входам (не более одного по каждому входу) и посылать несколько сообщений по своим выходам (не более одного по каждому выходу). Определяется ассоциативная композиция автоматов системы. Показывается, при каких ограничениях на автоматы и граф связей их композиция, т.е. сама система, детерминирована. Целью тестирования является покрытие переходов автоматов компонентов, которые достижимы при работе этих автоматов в системе. Предполагается, что при тестировании возможно наблюдение изменения состояний автоматов системы и передаваемых между ними сообщений. Полное тестирование системы автоматов без учёта гипотезы о связях может потребовать число тестовых воздействий порядка произведения чисел состояний автоматов компонентов, а с учётом гипотезы о связях — порядка суммы этих чисел. При равном числе состояний всех автоматов это даёт экспоненциальное уменьшение числа тестовых воздействий. При условии выполнения гипотезы о связях для детерминированной системы предлагается алгоритм генерации тестов, основанный на фильтрации тестов, генерируемых для покрытия всех переходов композиции. Тест отбрасывается, если он покрывает только такие переходы в компонентах системы, которые покрываются остающимися тестами. В заключение определяются направления дальнейших исследований.

Ключевые слова: ориентированные графы, покрытие графа, взаимодействующие автоматы, композиция автоматов, детерминизм, распределенные системы, тестирование, сети.

DOI: https://doi.org/10.15514/ISPRAS-2016-28(1)-9

Полный текст: PDF файл (469 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья

Образец цитирования: И. Б. Бурдонов, А. С. Косачев, “Система автоматов: условия детерминизма и тестирование”, Труды ИСП РАН, 28:1 (2016), 151–184

Цитирование в формате AMSBIB
\RBibitem{BurKos16}
\by И.~Б.~Бурдонов, А.~С.~Косачев
\paper Система автоматов: условия детерминизма и тестирование
\jour Труды ИСП РАН
\yr 2016
\vol 28
\issue 1
\pages 151--184
\mathnet{http://mi.mathnet.ru/tisp9}
\crossref{https://doi.org/10.15514/ISPRAS-2016-28(1)-9}
\elib{http://elibrary.ru/item.asp?id=26166321}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/tisp9
  • http://mi.mathnet.ru/rus/tisp/v28/i1/p151

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Труды института системного программирования РАН
    Просмотров:
    Эта страница:47
    Полный текст:9
    Литература:13

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018