|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
О возможностях автоматного описания параллельной композиции временных автоматов
А. С. Твардовский, А. В. Лапутенко Национальный исследовательский Томский государственный университет
Аннотация:
Конечные автоматы широко используются для анализа и синтеза дискретных систем. При описании систем, поведение которых зависит от времени, конечный автомат расширяется введением временных аспектов и вводится понятие временного автомата. В настоящей статье рассматривается проблема построения параллельной композиции для двух моделей временных автоматов, а именно, для автоматов с таймаутами и автоматов с временными ограничениями. Две эти формы временных автоматов не являются взаимозаменяемыми и являются более частными случаями общей модели временного автомата, содержащего как таймауты, так и временные ограничения. Мы также считаем, что все выше упомянутые модели временных автоматов имеют целочисленные выходные задержки (выходные таймауты). Автоматы-компоненты работают в режиме диалога, по завершении которого композиция выдаёт внешний выходной символ. При решении задач анализа для системы взаимодействующих конечных автоматов с использованием классических методов такая композиция обычно описывается единственным автоматом. В работе показывается, что в общем случае, в отличие от случая классических конечных автоматов, наличия «медленной внешней среды» и отсутствия осцилляций недостаточно для описания поведения композиции детерминированным автоматом с одной временной переменной, если входные символы могут поступать не только в целочисленные, но и рациональные моменты времени. Тем не менее, определяется класс систем, в которых каждое внешнее входное воздействие инициирует диалог между компонентами, что позволяет описать поведение такой композиции детерминированным автоматом с одной временной переменной. В частности, рассматривается последовательная композиция временных автоматов, которая удовлетворяет такому ограничению. Другое ограничение продиктовано наличием таймаутов, значение которого в каждом из состояний должно превышать величину выходной задержки при обработке любого перехода в этом состоянии.
Ключевые слова:
конечный автомат, входные и выходные таймауты, временные ограничения, композиция.
Образец цитирования:
А. С. Твардовский, А. В. Лапутенко, “О возможностях автоматного описания параллельной композиции временных автоматов”, Труды ИСП РАН, 30:1 (2018), 25–40
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/tisp293 https://www.mathnet.ru/rus/tisp/v30/i1/p25
|
Статистика просмотров: |
Страница аннотации: | 240 | PDF полного текста: | 96 | Список литературы: | 19 |
|