|
Труды института системного программирования РАН, 2017, том 29, выпуск 4, страницы 139–154
(Mi tisp240)
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Минимизация автоматов с таймаутами и временными ограничениями
А. С. Твардовский, Н. В. Евтушенко, М. Л. Громов Национальный исследовательский Томский государственный университет
Аннотация:
Конечные автоматы широко используются для анализа и синтеза управляющих систем. При описании систем, поведение которых зависит от времени, конечный автомат расширяется введением временных аспектов и вводится понятие временного автомата. В настоящей работе мы рассматриваем проблему минимизации автоматов с таймаутами и временными ограничениями, поскольку сложность многих задач в теории автоматов существенно зависит от размеров исследуемой системы. Поведение временного автомата может быть достаточно точно описано соответствующим конечным автоматом, и предлагаемый метод минимизации числа состояний системы основан на использовании такой конечно автоматной абстракции. Более того, далее мы минимизируем и временные аспекты автоматного описания, сокращая продолжительность таймаутов и число переходов с временными ограничениями. Мы также показываем, что для полностью определённого детерминированного временного автомата существует единственная минимальная (каноничная) форма, т. е. единственный приведённый по состояниям и временным аспектам автомат с таймаутами и временными ограничениями, поведение которого совпадает с исходным временным автоматом; например, такая минимальная форма может быть использована при построении проверяющих тестов для проверки функциональных и нефункциональных требований к тестируемой реализации. Предложенный метод к минимизации временных аспектов на основе конечно автоматной абстракции может быть применён и для частных случаев рассматриваемой модели, т. е. для минимизации детерминированных полностью определенных автоматов только с таймаутами или только с временными ограничениями.
Ключевые слова:
временные автоматы, приведённая форма, минимальная форма.
Образец цитирования:
А. С. Твардовский, Н. В. Евтушенко, М. Л. Громов, “Минимизация автоматов с таймаутами и временными ограничениями”, Труды ИСП РАН, 29:4 (2017), 139–154
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/tisp240 https://www.mathnet.ru/rus/tisp/v29/i4/p139
|
Статистика просмотров: |
Страница аннотации: | 186 | PDF полного текста: | 87 | Список литературы: | 30 |
|