Parallel composition of nondeterministic Finite State Machines with Timeouts.pdf Многие управляющие системы и системы обработки информации можно рассматривать как системы, преобразующие последовательности действий в одном алфавите в последовательности действий в другом алфавите. При синтезе и анализе подобных систем достаточно часто приходится моделировать функционирование системы с учетом временных аспектов, таких как скорость реакции системы, задержка выходного сигнала, таймаут по ожиданию входного сигнала и т.п. Вход-выходные модели с конечным числом состояний хорошо подходят для решения широкого класса задач синтеза и анализа таких последовательностных систем, поэтому одним из естественных и перспективных путей развития подобных моделей для учета временных аспектов поведения является расширение классических моделей специальными временными функциями. Задача описания взаимодействующих дискретных систем возникает в различных приложениях. В [1] предлагается неформальное описание композиции детерминированных временных автоматов. В данной статье мы формализуем предложенное описание взаимодействия, а также предлагаем такое расширение модели временного автомата, которое позволило бы описать композицию недетерминированных компонент. 1. Временной автомат с таймаутами Через N обозначается множество натуральных чисел. Временным автоматом [1], который далее будем называть просто автоматом, называется конечный автомат с таймаутами, т.е. семёрка S = (S, I, O, s0, XS, AS, oS), где пятёрка (S, I, O, s0, XS) есть классический конечный автомат, в котором S - конечное непустое множество состояний с выделенным начальным состоянием s0, I и O - конечные входной и выходной алфавиты соответственно, XS с S х I х S х O - отношение переходов. Кроме того, функция задержки входного символа AS: S ^ S х (N и {да}) определяет для каждого состояния максимальное время ожидания входного символа (входной таймаут), функция задержки выходного символа oS: XS ^ ({0} и N) определяет для каждого перехода необходимый интервал времени для выполнения соответствующего перехода и выработки выходного символа в ответ на поступившее входное воздействие (выходной таймаут). Таймаут для входного символа означает, что если в некотором состоянии автомата входной сигнал не поступает в течение определенного времени, то автомат может изменить своё состояние, не производя выходного символа. Отметим, что если для некоторого состояния s имеет место AS (5) = (5', то s = s', и автомат в этом состоянии может находиться бесконечно долго в ожидании входного воздействия. Каждому временному автомату можно поставить в соответствие внутреннюю целочисленную переменную-таймер, отсчитывающую количество единиц времени, прошедших после достижения автоматом текущего состояния или после получения автоматом последнего входного символа. Сброс таймера происходит каждый раз при получении автоматом входного символа и при смене состояния автомата как в результате перехода под действием входного символа с выдачей выходного символа, так и в результате перехода по таймауту. Отметим, что, по определению временного автомата, входной символ может поступить на автомат в любой действительный момент времени; соответственно будет вычислено следующее состояние автомата и выдаваемый выходной символ. При этом, в силу того что таймауты могут иметь только целочисленные значения, любой входной символ, поступивший на автомат в некоторый момент времени в интервале [n, n + 1), n е {0} u N, обрабатывается автоматом так же, как входной символ, поступивший в момент времени n. Временной автомат S называется детерминированным, если для любых s1 е S и i е I существует не более одной пары (s2, o) е S х O, такой что (s1, i, s2, o) е XS, в противном случае автомат называется недетерминированным. Автомат называется полностью определенным, если для любых s1 е S и i е I существует пара (s2, o) е S х O, такая что (s1, i, s2, o) е XS, в противном случае автомат называется частичным. Для описания поведения временного автомата с учетом временных аспектов вводятся понятия временного входного символа и временного выходного символа. Временной входной символ (i, t) е I х ({0} u N) показывает, что входной символ i подается в тот момент, когда значение временной переменной равно t. Временной выходной символ (o, k) е O х ({0} u N) показывает, что символ o выдается автоматом через k единиц времени после получения входного символа. Для того чтобы вычислить реакцию автомата на временной входной символ (i, t), необходимо сначала определить, в каком состоянии будет находиться автомат в момент подачи входного символа i [1]. Пусть символ (i, t) поступает на автомат в состоянии s. Рассмотрим последовательность переходов по таймаутам AS (s) = (s1, T1), As (s 1) = (s2, T2), ..., As (s^) = (sp, Tp), такую что Ti + T2 + ... + T- < t, но Ti + T2 + ... + Tp > t. В этом случае входной символ i появится на входе автомата после того, как автомат перейдет в состояние sp. Если AS (s) = (s, да), то sp = s при любом t. Таким образом, в результате подачи символа (i, t) в состоянии s автомат произведет выходной символ o через k единиц времени, если и только если (sp, i, s', o) е XS и aS ((sp, i, s', o)) = k. Таким образом, выходной реакцией автомата S в состоянии s на входной символ (i, t) является символ (o, k), и после выдачи этого символа автомат перейдет в состояние s'. Рассмотрим временную входную последовательность а = (i1, t1)(i2, t2)...(in, tn) и временную выходную последовательность в = (o1, k1)(o2, k2)...(on, kn). Если в автомате S существует такая последовательность переходов, что при подаче в состоянии s последовательности а автомат может произвести в ответ последовательность в, то пара ав называется временной вход-выходной последовательностью или временной трассой автомата S в состоянии s. Множество всех временных трасс автомата S в состоянии s обозначается traceS(s). Два состояния s и p полностью определенных временных автоматов S и P называются эквивалентными, если множества трасс в этих состояниях совпадают, т.е. traceS(s) = traceP(p). Автоматы S и P называются эквивалентными, если их начальные состояния эквивалентны. Автомат S есть редукция автомата P, обозначение S < P, если traceS(s0) с traceP(p0). Множество временных трасс автомата S = (S, I, O, s0, XS, AS, cS) можно представить как язык полуавтомата Aut(S) = (S u Stu (S х I) u Sk, Iu O u{1}, s0, 5s, S u ST), в котором специальный символ 1

Скачать электронную версию публикации