Построение каскадной параллельной композиции временных автоматов с использованием BALM-II

Аннотация

В данной работе мы рассмотрели задачу построения каскадной параллельной композиции временных автоматов. Построение такой композиции можно свести к поэтапному построению бинарной параллельной композиции. Известно, что если каждая из компонент бинарной параллельной композиции есть временной автомат с константными задержками выходов, то результатом композиции может быть временной автомат, множество задержек выходных символов которого бесконечно и задано при помощи конечного множества линейных функций. Поэтому задача построения каскадной композиции временных автоматов с константными задержками выходов сводится к построению ряда бинарных параллельных композиций временных автоматов, задержки выходов которых заданы либо в виде констант, либо в виде множества линейных функций. В данной работе мы уточняем определение временного автомата, обращая особое внимание на описание задержки выходного символа. В качестве инструмента для построения композиции мы используем balm-ii, и поэтому рассматриваем переход от временного автомата с задержками выходов в виде множества линейных функций к соответствующему полуавтомату. Мы предлагаем свою процедуру построения полуавтомата, которая, в отличие от известной процедуры, не требует последующей детерминизации полученного полуавтомата. Кроме того, мы пошагово описываем, каким образом построить композицию соответствующих полуавтоматов при помощи balm-ii, а также обсуждаем процедуру обратного преобразования от полуавтомата композиции к временному автомату, отмечая некоторые нюансы, связанные с композицией временных автоматов с задержками выходов в виде множества линейных функций. В работе приведён пример, иллюстрирующий построение каскадной параллельной композиции временных автоматов.