Сигнальный автомат

В теории автоматов , области информатики , сигнальный автомат — это конечный автомат, расширенный конечным набором действительных часов. Во время работы сигнального автомата значения тактовых импульсов увеличиваются с одинаковой скоростью. В ходе переходов автомата значения часов можно сравнивать с целыми числами. Эти сравнения формируют защитные меры, которые могут включать или отключать переходы и тем самым ограничивать возможное поведение автомата. Кроме того, часы можно сбросить.

Пример

Прежде чем формально определить, что такое сигнальный автомат, приведем пример. Рассмотрим язык ${\mathcal {L}}$ сигналов в двоичном алфавите $\{A,B\}$, который содержит сигналы $\gamma$ такой, что:

• $A$ появляется в единичных интервалах. То есть набор времен $\{t\mid \gamma (t)=A\}$ является дискретным, и
• $A$ появляется хотя бы один раз в течение каждого интервала длиной один.

Этот язык может быть принят автоматом, изображенным рядом.

Сигнальный автомат, обеспечивающий выполнение A дискретно и хотя бы один раз за единицу времени.

Что касается конечного автомата, входящие стрелки обозначают начальные местоположения, а двойной круг — принимающие местоположения. Однако, в отличие от конечных автоматов, буквы встречаются в местах, а не в переходах. Это связано с тем, что буквы выдаются непрерывно, а переходы выполняются дискретно. Символ $x$ представляет собой часы . Эти часы позволяют измерять время с момента последнего посещения $A$ был излучен. Таким образом $x=0$ гарантирует, что $A$ излучается дискретно. И $1>x$ гарантирует, что не более единицы времени может пройти без $A$ происходит.

Формальное определение

Сигнальный автомат

Формально сигнальный автомат представляет собой кортеж ${\mathcal {A}}=\langle \Sigma ,L,L_{0},C,F,\alpha ,\beta ,E\rangle$ который состоит из следующих компонентов:

• $\Sigma$ — это конечное множество, алфавитом или действиями называемое ${\mathcal {A}}$.
• $L$ является конечным множеством . Элементы $L$ называются местами или состояниями ​ ${\mathcal {A}}$.
• $C$ представляет собой конечное множество, часами называемое ${\mathcal {A}}$.
• $L_{0}\subseteq L$ это набор стартовых локаций.
• $F\subseteq L$ набор принимающих пунктов.
• $\alpha :L\to \Sigma$ который связывает букву с каждым местоположением.
• $\beta :L\to {\mathcal {B}}(C)$ которые связывают ограничения часов с каждым местоположением, и
• $E\subseteq L\times {\mathcal {P}}(C)\times L$ представляет собой набор ребер, переходами называемых ${\mathcal {A}}$, где
  • ${\mathcal {P}}(C)$ это мощности набор $C$.

Край $(\ell ,r,\ell ')$ от $E$ это переход из локаций $\ell$ к $\ell '$ который сбрасывает часы $r$.

Расширенное состояние

Пара с локацией $\ell$ и оценка часов $\nu$ называется либо расширенным состоянием , либо состоянием .

Заметим, что слово состояние при этом неоднозначно, поскольку, в зависимости от автора, оно может обозначать либо пару, либо элемент $L$. Для ясности в этой статье будет использоваться термин «расположение ». для обозначения элемента $L$ и термин «расширенное местоположение» для пар.

В этом заключается одно из самых больших различий между сигнальными автоматами и конечными автоматами . В конечном автомате в какой-то момент выполнения состояние полностью описывается количеством прочитанных букв и конечным числом возможных значений, которые на самом деле называются «состояниями». Это означает, что, учитывая состояние и суффикс читаемого слова, оставшаяся часть серии полностью определена. Таким образом, в названии «конечные автоматы» появилось слово «конечный». Однако, как поясняется в разделе «Выполнение» ниже, для возобновления используются часы, определяющие, какие переходы можно предпринять. Таким образом, чтобы узнать состояние автомата, необходимо и сейчас, в каком месте вы находитесь, и оценку часов.

Бегать

Что касается конечных автоматов, прогон по сути представляет собой последовательность мест, в которой существует переход между двумя местами. Однако следует подчеркнуть два различия. Буква определяется не переходом, а местами; это связано с тем, что буквы излучаются непрерывно, а переходы выполняются дискретно. Проходит некоторое время в локации; ограничения часов, маркирующие местоположение или его преемника, могут ограничивать время, проведенное в одном месте.

Прогон – это последовательность вида ${\xrightarrow[{\nu _{0}}]{C}}(\ell _{0},I_{0}){\xrightarrow[{\nu _{1}}]{r_{1}}}(\ell _{1},I_{1})\dots$ удовлетворяющие некоторым ограничениям. Прежде чем сформулировать эти ограничения, вводятся некоторые обозначения. Последовательности дискретны, но представляют собой непрерывные события. Непрерывная версия последовательностей $(\sigma _{i})$, $(\nu _{i})$, $(\ell _{i})$ теперь представлены. Позволять $i\geq 0$ интегральный и $t\in I_{i}$, затем

• позволять $\sigma '_{t}$ быть равным $\sigma _{i}$,
• позволять $\nu '_{t}$ быть $\nu _{i}+t-\lceil I_{i}\rceil$ с $\lceil I_{i}\rceil$ является нижней границей интервала $I_{i}$,
• позволять $\ell '_{t}=\ell _{i}$.

Ограничения, которым удовлетворяет run, для каждого $i\geq 0$ интегральный и $t\geq 0$ настоящий:

• $\ell _{0}\in L_{0}$,
• $(\ell _{i},r_{i},\ell _{i+1})\in E$,
• $\nu _{i+1}=(\nu _{i}+\mid I_{i}\mid )[r_{i}\rightarrow 0]$,
• $\nu '_{t}\models \beta (\ell '_{t})$.

Сигналом , определяемым этим прогоном, является функция $\sigma '$ определено выше. Говорят, что прогон, определенный выше, является прогоном для сигнала $\sigma '$.

Понятие принятия серии определяется как в конечных автоматах для конечных слов, так и в автоматах Бюхи для бесконечных слов. То есть, если $w$ имеет конечную длину $n$, то прогон принимается, если $\ell _{n}\in F$. Если слово бесконечно, то прогон принимается тогда и только тогда, когда существует бесконечное количество позиций. $i$ такой, что $\ell _{i}\in F$.

Принимаемые сигналы и язык

Сигнал $\gamma$ говорят, что он принимается сигнальным автоматом ${\mathcal {A}}$ если существует серия ${\mathcal {A}}$ на $\gamma$ принимая это. Набор сигналов, принимаемых ${\mathcal {A}}$ называется языком, принятым ${\mathcal {A}}$ и обозначается ${\mathcal {S(A)}}$.

Детерминированный сигнальный автомат

Как и в случае конечного автомата и автомата Бюхи, сигнал-автомат может быть детерминированным или недетерминированным. Интуитивно быть детерминированным – это одно и то же значение в каждом из этих случаев. Это означает, что набор начальных местоположений является одноэлементным, и что, учитывая расширенное состояние $s$и письмо $a$, существует только одно возможное расширенное состояние, которого можно достичь из $s$ читая $a$. Точнее, либо в локации можно оставаться дольше, либо существует не более одной возможной локации-преемника.

Формально это можно определить следующим образом:

• $L_{0}$ является синглтоном
• для каждого места $\ell \in L$, для каждого перехода $(\ell ,r,\ell ')\in E$, две следующие зоны не пересекаются:
  • зона, определяемая ограничением часов $\beta (\ell )$,
  • зона, определяемая ограничением часов $\beta (\ell ')$ где ограничения на часы $r$ удалены,
• для каждого перехода локации $(\ell ,r',\ell ')\in E$ и $(\ell ,r'',\ell '')\in E$, две следующие зоны не пересекаются:
  • зона, определяемая ограничением часов $\beta (\ell ')$ где ограничения на часы $r'$ удалены,
  • зона, определяемая ограничением часов $\beta (\ell '')$ где ограничения на часы $r''$ удалены,

Упрощенные сигнальные автоматы

В зависимости от авторов точное определение сигнальных автоматов может немного отличаться. Сейчас даны два таких определения.

Полуоткрытые интервалы

Чтобы упростить определение прогона, некоторые авторы требуют, чтобы каждый интервал прогона был закрыт справа и открыт слева. Это ограничивает автоматы приемом только сигналов, базовый раздел которых удовлетворяет тому же свойству. Однако это гарантирует, что в каждый момент времени $t\geq 0$, $\lim _{t\leftarrow x^{+}}f(x)=f(t)$ для $f$ представляющий любую функцию $\sigma '$, $\nu '$ или $\ell '$ представлено выше.

Двудольный сигнальный автомат

Двудольный сигнальный автомат — это сигнальный автомат, в котором прогон чередуется между открытыми интервалами и сингулярными интервалами (т. е. интервалами, которые являются одиночными). Это гарантирует, что граф, лежащий в основе автомата, является двудольным графом и, таким образом, множество мест можно разделить на $\{L^{o},L^{s}\}$, набор открытых локаций и единичных локаций. Поскольку первый интервал содержит 0, он не может быть открытой локацией, отсюда следует, что $L_{0}\subseteq L^{s}$. Чтобы гарантировать, что каждое отдельное местоположение действительно уникально, для каждого местоположения $\ell$, должны быть часы $x_{\ell }$ который сбрасывается при вводе $\ell$ и такое, что ограничение часов $\ell$ содержит $x=0$.

Любой сигнальный автомат можно преобразовать в эквивалентный двудольный сигнальный автомат. Достаточно заменить каждую локацию $\ell$ по паре локаций $(\ell ^{o},\ell ^{s})$ и представить новые часы $x$, такой, что для каждого $\ell$, $x_{\ell ^{s}}=x$.

Рядом изображен двудольный автомат, эквивалентный сигнальному автомату из раздела примеров. Прямоугольные состояния представляют собой отдельные местоположения.

Автомат двудольного сигнала, обеспечивающий выполнение A дискретно и хотя бы один раз за единицу времени.

Синхронизация автоматов

Понятие произведения конечного автомата распространяется на сигнальный автомат. Однако такое произведение называется синхронизацией автомата, чтобы подчеркнуть тот факт, что время должно проходить одинаково в обоих рассматриваемых автоматах. Основное различие между синхронизацией и произведением состоит в том, что когда два конечных автомата читают одно и то же слово, они выполняют переход одновременно. Это уже не относится к сигнальным автоматам, поскольку они могут совершать переход в произвольное время. Таким образом, отношение перехода сигнального автомата может позволить осуществить переход в одном или двух автоматах.

Позволять ${\mathcal {A}}^{1}=\langle \Sigma ,L^{1},L_{0}^{1},C^{1},F^{1},\alpha ^{1},\beta ^{1},E^{1}\rangle$ и ${\mathcal {A}}^{2}=\langle \Sigma ,L^{2},L_{0}^{2},C^{2},F^{2},\alpha ^{2},\beta ^{2},E^{2}\rangle$ два сигнальных автомата, их синхронизация - сигнальный автомат ${\mathcal {A}}1\otimes {\mathcal {A}}^{2}=\langle \Sigma ,\{(\ell ^{1},\ell ^{2})\in L^{1}\otimes L^{2}\mid \alpha ^{1}(\ell ^{1})=\alpha ^{2}(\ell ^{2})\},L_{0}^{1}\otimes L_{0}^{2},C^{1}\cup C^{2},F^{1}\otimes F^{2},(\ell ^{1},\ell ^{2})\mapsto \alpha ^{1}(\ell ^{1}),(\ell ^{1},\ell ^{2})\mapsto \beta ^{1}(\ell ^{1})\land \beta ^{2}(\ell ^{2}),E\rangle$, где $E$ содержит следующие переходы:

• $((\ell ^{1},\ell ^{2}),r^{1},(\ell ^{\prime 1},\ell ^{2})$ для $(\ell ^{1},r,\ell ^{\prime 1})\in E^{1}$, и аналогично для $E^{2}$,
• $((\ell ^{1},\ell ^{2}),r^{1}\cup r^{2},(\ell ^{\prime 1},\ell ^{\prime 2})$ для $(\ell ^{1},r,\ell ^{\prime 1})\in E^{1}$ и $(\ell ^{2},r,\ell ^{\prime 2})\in E^{2}$.

Разница с синхронизированными автоматами

Автоматы с таймером — это еще одно расширение конечных автоматов, которое добавляет к словам понятие времени. Теперь мы сформулируем некоторые основные различия между синхронизированными и сигнальными автоматами.

В таймерных автоматах буквы выдаются на переходах, а не в локациях. Как объяснялось выше при сравнении сигнальных автоматов с конечными автоматами, буквы испускаются при переходах, когда слова испускаются дискретно, что касается слов и синхронизированных слов, тогда как они испускаются в местах, когда буквы испускаются непрерывно, как и для сигналов.

В автоматах с таймером охранники проверяются только на переходах. Это упрощает определение детерминированного автомата, поскольку означает, что ограничение должно быть удовлетворено до перезапуска часов.

См. также

• Автомат с таймером