|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
On reduced forms of initialized Finite State Machines with timeouts
[О минимизации инициальных автоматов с таймаутами]
A. S. Tvardovskiia, N. V. Yevtushenkobc a National Research Tomsk State University
b National Research University Higher School of Economics
c Ivannikov Institute for System Programming of the Russian Academy of Sciences
Аннотация:
Модели с конечным числом состояний широко используются при решении задач анализа и синтеза дискретных систем, и минимизация конечных автоматов является известной проблемой оптимизации, которая позволяет уменьшить количество состояний конечного автомата, описывающего поведение дискретной системы, на основе использования его приведенной формы. Такая форма единственна с точностью до изоморфизма для классических конечных автоматов, что, в частности, является основой для соответствующих методов синтеза тестов с гарантированной полнотой относительно «черного ящика», таких как W-метод и его модификации. Поскольку поведение современного программного и аппаратного обеспечения зачастую зависит от временных аспектов, в настоящее время классические автоматы расширяются временной переменной и связанными с ней входными и выходными таймаутами. Существующие подходы к минимизации временных автоматов охватывают оптимизацию как состояний, так и временных аспектов, и позволяют получить единственную минимальную форму для неинициальных детерминированных временных автоматов. В то же время для инициальных временных автоматов, т.е. автоматов с выделенным начальным состоянием, могут существовать различные попарно неизоморфные минимальные формы. В настоящей работе мы определяем классы инициальных временных автоматов, для которых минимальная форма единственна с точностью до изоморфизма.
Ключевые слова:
временные автоматы, минимизация, таймауты, инициальные автоматы.
Образец цитирования:
A. S. Tvardovskii, N. V. Yevtushenko, “On reduced forms of initialized Finite State Machines with timeouts”, Труды ИСП РАН, 32:2 (2020), 125–134
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/tisp503 https://www.mathnet.ru/rus/tisp/v32/i2/p125
|
Статистика просмотров: |
Страница аннотации: | 112 | PDF полного текста: | 67 | Список литературы: | 9 |
|