О возможностях автоматного описания параллельной композиции временных автоматов

Конечные автоматы широко используются для анализа и синтеза дискретных систем. При описании систем, поведение которых зависит от времени, конечный автомат расширяется введением временных аспектов и вводится понятие временного автомата. В настоящей статье рассматривается проблема построения параллельной композиции для двух моделей временных автоматов, а именно, для автоматов с таймаутами и автоматов с временными ограничениями. Две эти формы временных автоматов не являются взаимозаменяемыми и являются более частными случаями общей модели временного автомата, содержащего как таймауты, так и временные ограничения. Мы также считаем, что все выше упомянутые модели временных автоматов имеют целочисленные выходные задержки (выходные таймауты). Автоматы-компоненты работают в режиме диалога, по завершении которого композиция выдаёт внешний выходной символ. При решении задач анализа для системы взаимодействующих конечных автоматов с использованием классических методов такая композиция обычно описывается единственным автоматом. В работе показывается, что в общем случае, в отличие от случая классических конечных автоматов, наличия «медленной внешней среды» и отсутствия осцилляций недостаточно для описания поведения композиции детерминированным автоматом с одной временной переменной, если входные символы могут поступать не только в целочисленные, но и рациональные моменты времени. Тем не менее, определяется класс систем, в которых каждое внешнее входное воздействие инициирует диалог между компонентами, что позволяет описать поведение такой композиции детерминированным автоматом с одной временной переменной. В частности, рассматривается последовательная композиция временных автоматов, которая удовлетворяет такому ограничению. Другое ограничение продиктовано наличием таймаутов, значение которого в каждом из состояний должно превышать величину выходной задержки при обработке любого перехода в этом состоянии.