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

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

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



Модел. и анализ информ. систем:
Год:
Том:
Выпуск:
Страница:
Найти






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


Моделирование и анализ информационных систем, 2020, том 27, номер 4, страницы 376–395
DOI: https://doi.org/10.18255/1818-1015-2020-4-376-395
(Mi mais723)
 

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

Theory of computing

Синтез установочных последовательностей для автоматов с временными ограничениями

А. С. Твардовскийa, Н. В. Евтушенкоbc

a Национальный исследовательский Томский Государственный университет, пр. Ленина, д. 36, г. Томск, 634050 Россия
b Институт системного программирования РАН, ул. А. Солженицына, д. 25, г. Москва, 109004 Россия
c Национальный исследовательский университет «Высшая школа экономики», ул. Мясницкая, д. 20, г. Москва, 101000 Россия
Список литературы:
Аннотация: Идентификация состояний является хорошо известной задачей теории конечных автоматов, и установочные последовательности, которые позволяют идентифицировать текущее состояние конечного автомата, широко используются в областях тестирования и верификации программного и аппаратного обеспечения. Для автоматов различных классов, полностью определенных и частичных, детерминированных и недетерминированных, установлены необходимые и достаточные условия существования безусловных и адаптивных установочных последовательностей и предложены алгоритмы их синтеза, если такая последовательность существует. В настоящее время при верификации и тестировании программного и аппаратного обеспечения необходимо учитывать временные аспекты, что приводит к расширению автоматных моделей временными переменными. В настоящей работе мы исследуем задачи проверки существования и синтеза безусловных и адаптивных установочных последовательностей для автоматов с временными ограничениями и показываем, что оценки на длину таких последовательностей совпадают с оценками для классических конечных автоматов. Предлагаемый подход основан на использовании конечно-автоматной абстракции временного автомата, то есть описании временного автомата соответствующим конечным автоматом, который сохраняет свойства временного автомата относительно установочных последовательностей.
Ключевые слова: конечный автомат, временные ограничения, конечно-автоматная абстракция, установочная последовательность.
Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 19-07-00327
Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 19-07-00327.
Поступила в редакцию: 09.11.2020
Исправленный вариант: 30.11.2020
Принята в печать: 16.12.2020
Тип публикации: Статья
УДК: 519.7
MSC: 68Q45
Образец цитирования: А. С. Твардовский, Н. В. Евтушенко, “Синтез установочных последовательностей для автоматов с временными ограничениями”, Модел. и анализ информ. систем, 27:4 (2020), 376–395
Цитирование в формате AMSBIB
\RBibitem{TvaEvt20}
\by А.~С.~Твардовский, Н.~В.~Евтушенко
\paper Синтез установочных последовательностей для автоматов с временными ограничениями
\jour Модел. и анализ информ. систем
\yr 2020
\vol 27
\issue 4
\pages 376--395
\mathnet{http://mi.mathnet.ru/mais723}
\crossref{https://doi.org/10.18255/1818-1015-2020-4-376-395}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/mais723
  • https://www.mathnet.ru/rus/mais/v27/i4/p376
  • Эта публикация цитируется в следующих 1 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Моделирование и анализ информационных систем
    Статистика просмотров:
    Страница аннотации:110
    PDF полного текста:55
    Список литературы:21
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024