Сборники трудов ИСП РАН


Эксперименты по построению параллельной композиции временных автоматов

А. Сотников (ТГУ, Томск, Россия)
Н. Шабалдина (ТГУ, Томск, Россия)
М. Громов (ТГУ, Томск, Россия)

Аннотация

В данной работе мы продолжаем наши исследования параллельной композиции временных конечных автоматов. Мы рассматриваем композицию временных автоматов с таймаутами и задержками выходных символов. Для того чтобы оценить, насколько часто в параллельной композиции недетерминированных временных автоматов (с таймаутами и без таймаутов) возникают бесконечные множества задержек выходных символов, мы провели компьютерные эксперименты. Для проведения таких экспериментов мы реализовали два инструмента: первый позволяет преобразовать временной конечный автомат в полуавтомат (данный инструмент встроен в BALM-II), второй позволяет преобразовать глобальный полуавтомат композиции во временной автомат. Ориентируясь на известные работы  по данной тематике, мы описываем бесконечные множества задержек выходных символов конечным образом, а именно, при помощи линейных функций, и нужно знать, как часто такое множество линейных функций возникает, чтобы оценить важность дальнейших исследований параллельной композиции временных автоматов (особенно случая каскадной композиции). Результаты экспериментов показали, что в значительном количестве случаев (около 50 %) временной автомат композиции содержит бесконечное множество задержек выходных символов. Кроме того, мы оценили размер глобального полуавтомата и автомата композиции. При проведении экспериментов мы не рассматривали глобальные полуавтоматы с большим числом состояний (более 10000).

Ключевые слова

временные конечные автоматы; параллельная композиция; BALM-II

Издание

Труды Института системного программирования РАН, том 29, вып. 3, 2017, стр. 233-246.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2017-29(3)-13

Полный текст статьи в формате pdf (на английском) Вернуться к содержанию тома