|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Theory of computing
Синтез установочных последовательностей для автоматов с временными ограничениями
А. С. Твардовскийa, Н. В. Евтушенкоbc a Национальный исследовательский Томский Государственный университет, пр. Ленина, д. 36, г. Томск, 634050 Россия
b Институт системного программирования РАН, ул. А. Солженицына, д. 25, г. Москва, 109004 Россия
c Национальный исследовательский университет «Высшая школа экономики», ул. Мясницкая, д. 20, г. Москва, 101000
Россия
Аннотация:
Идентификация состояний является хорошо известной задачей теории конечных автоматов, и установочные последовательности, которые позволяют идентифицировать текущее состояние конечного автомата, широко используются в областях тестирования и верификации программного и аппаратного обеспечения. Для автоматов различных классов, полностью определенных и частичных, детерминированных и недетерминированных, установлены необходимые и достаточные условия существования безусловных и адаптивных установочных последовательностей и предложены алгоритмы их синтеза, если такая последовательность существует. В настоящее время при верификации и тестировании программного и аппаратного обеспечения необходимо учитывать временные аспекты, что приводит к расширению автоматных моделей временными переменными. В настоящей работе мы исследуем задачи проверки существования и синтеза безусловных и адаптивных установочных последовательностей для автоматов с временными ограничениями и показываем, что оценки на длину таких последовательностей совпадают с оценками для классических конечных автоматов. Предлагаемый подход основан на использовании конечно-автоматной абстракции временного автомата, то есть описании временного автомата соответствующим конечным автоматом, который сохраняет свойства временного автомата относительно установочных последовательностей.
Ключевые слова:
конечный автомат, временные ограничения, конечно-автоматная абстракция, установочная последовательность.
Поступила в редакцию: 09.11.2020 Исправленный вариант: 30.11.2020 Принята в печать: 16.12.2020
Образец цитирования:
А. С. Твардовский, Н. В. Евтушенко, “Синтез установочных последовательностей для автоматов с временными ограничениями”, Модел. и анализ информ. систем, 27:4 (2020), 376–395
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mais723 https://www.mathnet.ru/rus/mais/v27/i4/p376
|
Статистика просмотров: |
Страница аннотации: | 91 | PDF полного текста: | 47 | Список литературы: | 10 |
|