Коммуникационный конечный автомат

В информатике взаимодействующий конечный автомат — это конечный автомат, помеченный операциями «получения» и «отправки» по некоторому алфавиту каналов. Их познакомили Бранд и Зафиропуло. ^[1] и может использоваться в качестве модели параллельных процессов, таких как сети Петри . Коммуникационные конечные автоматы часто используются для моделирования протокола связи, поскольку они позволяют обнаруживать основные ошибки проектирования протокола, включая ограниченность, взаимоблокировки и неопределенные приемы. ^[2]

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

Коммуникационные конечные автоматы могут быть более мощными, чем конечные автоматы, в ситуациях, когда задержка распространения не является незначительной (так что несколько сообщений могут передаваться одновременно) и в ситуациях, когда естественно описать стороны протокола и среду связи. как отдельные сущности. ^[1]

Коммуникационная иерархическая машина состояний

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

Однако было доказано, что сосуществование иерархии и параллелизма по своей сути обходится включением языка, языковой эквивалентностью и всей универсальностью. ^[3]

Определение

Протокол

Для произвольного положительного целого числа $N$ , протокол ^[1]^: 3 с $N$ процесс(ы) представляет собой четверку $\{(S_{i})_{i=1}^{N},\ (o_{i})_{i=1}^{N},\ (M_{i,j})_{i,j=1}^{N},\ ({\mathtt {succ}})_{i=1}^{N}\}$ с:

$(S_{i})_{i=1}^{N}$ , последовательность $N$ непересекающиеся конечные множества. Каждый набор используется для представления процесса, а каждый элемент $S_{i}$ представляет собой возможное состояние $i$ -й процесс.
$(o_{i})_{i=1}^{N}$ (с $o_{i}\in S_{i}$ ), последовательность, представляющая начальное состояние каждого процесса.
$(M_{i,j})_{i,j=1}^{N}$ , конечная последовательность $N^{2}$ непересекающиеся конечные множества такие, что каждое множество $M_{i,j}$ представляет возможные сообщения, которые могут быть отправлены из процесса $i$ обрабатывать $j$ . Если $i=j$ , затем $M_{i,j}$ пусто.
$({\mathtt {succ}})_{i=1}^{N}:S_{i}\times \bigcup _{j=1}^{N}\left(M_{j,i}^{[+]}\cup M_{i,j}^{[-]}\right)\mapsto S_{i}$ представляет собой последовательность функций перехода. Каждая функция моделирует переход, который можно совершить, отправив или получив любое сообщение. Что касается процесса $i$ , символ $[+]$ используется для обозначения сообщения, которое может быть получено и $[-]$ сообщение, которое можно отправить.

Глобальное состояние

Глобальное состояние — это пара $\langle S,C\rangle$ где

$S=(s_{1},...,s_{N})$ представляет собой упорядоченную совокупность состояний, каждое из которых $s_{i}$ представляет собой состояние $i$ -й процесс.
$C$ это $N\times N$ матрица такая, что каждый $c_{i,j}\in C$ является подпоследовательностью $M_{i,j}$ .

Начальное глобальное состояние представляет собой пару $\langle O,\mathrm {E} \rangle$ где

$O=(o_{1},...,o_{N})$
$\mathrm {E}$ определяется как $N\times N$ матрица такая, что для всех $i,j\in \{1,...,N\}$ , $E_{i,j}$ равно пустому слову, $\epsilon$ .

Шаг

Существует два типа шагов: этапы получения сообщения и этапы отправки сообщений.

Шаг, на котором $j$ процесс получения сообщенияранее отправленный $i$ -й процесс представляет собой пару вида $\left\langle (s_{1},\dots ,s_{j},\dots ,s_{n}),\left({\begin{array}{lll}c_{1,1}&\dots &c_{1,n}\\\dots &\dots &\dots \\\dots &m_{i,j}c_{i,j}&\dots \\\dots &\dots &\dots \\c_{n,1}&\dots &c_{n,n}\end{array}}\right)\right\rangle \vdash \left\langle (s_{1},\dots ,s'_{j},\dots ,s_{n}),\left({\begin{array}{lll}c_{1,1}&\dots &c_{1,n}\\\dots &\dots &\dots \\\dots &c_{i,j}&\dots \\\dots &\dots &\dots \\c_{n,1}&\dots &c_{n,n}\end{array}}\right)\right\rangle$ когда ${\mathtt {succ}}_{i}(s_{j},+m_{i,j})=s'_{j}$ , с $m'_{i,j}\in M_{i,j}$ . Аналогично, пара, в которой сообщение отправляется $i$ -й процесс к $j$ -й является парой вида $\left\langle (s_{1},\dots ,s_{i},\dots ,s_{n}),\left({\begin{array}{lll}c_{1,1}&\dots &c_{1,n}\\\dots &\dots &\dots \\\dots &c_{i,j}&\dots \\\dots &\dots &\dots \\c_{n,1}&\dots &c_{n,n}\end{array}}\right)\right\rangle \vdash \left\langle (s_{1},\dots ,s'_{i},\dots ,s_{n}),\left({\begin{array}{lll}c_{1,1}&\dots &c_{1,n}\\\dots &\dots &\dots \\\dots &m_{i,j}c_{i,j}&\dots \\\dots &\dots &\dots \\c_{n,1}&\dots &c_{n,n}\end{array}}\right)\right\rangle$ когда ${\mathtt {succ}}_{i}(s_{i},-m_{i,j})=s'_{i}$

Бегать

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

Говорят, что глобальное государство $\langle S,C\rangle$ достижим , если существует пробег, проходящий через это состояние.

Проблемы

С введением самой концепции было доказано, что, когда два конечных автомата обмениваются сообщениями только одного типа, могут быть определены и идентифицированы ограниченность, взаимоблокировки и неопределённое состояние приема, в то время как это не тот случай, когда автоматы обмениваются данными с двумя или несколько типов сообщений. Позже было дополнительно доказано, что когда только один конечный автомат обменивается сообщениями одного типа, в то время как общение его партнера является неограниченным, мы все равно можем решить и определить ограниченность, взаимоблокировки и неопределенное состояние приема. ^[2]

Далее было доказано, что когда отношение приоритета сообщения пусто, ограниченность, взаимоблокировки и неопределённое состояние приема могут быть определены даже при условии, что в связи между конечными автоматами имеется два или более типов сообщений. ^[4]

Ограниченность, взаимоблокировки и неопределенное состояние приема все разрешимы за полиномиальное время (что означает, что конкретная проблема может быть решена за приемлемое, а не бесконечное количество времени), поскольку проблемы решения, относящиеся к ним, являются полными в недетерминированном лог-пространстве. ^[2]

Расширения

Некоторые рассматриваемые расширения:

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

Канальная система

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

Формально, учитывая протокол $\langle (S_{i})_{i=1}^{n},(o_{i})_{i=1}^{n},(M_{i,j})_{i,j=1}^{n},({\mathtt {succ}})_{i}\rangle$ , связанная с ним система каналов $\langle \prod (S_{i})_{i=1}^{n},(o_{i})_{i=1}^{n},\bigcup _{i,j=1}^{n}(M_{i,j}),\Delta \rangle$ , где $\Delta$ это набор $((s_{1},\dots ,s_{j},\dots ,s_{n}),?m_{i,j},(s_{1},\dots ,{\mathtt {succ}}_{j}(s_{j},+m_{i,j}),\dots ,s_{n})$ и из $((s_{1},\dots ,s_{i},\dots ,s_{n}),!m_{i,j},(s_{1},\dots ,{\mathtt {succ}}_{i}(s_{i},-m_{i,j}),\dots ,s_{n})$ .

Ссылки

^ Jump up to: ^а ^б ^с ^д Д. Бранд и П. Зафиропуло. Об общении конечных автоматов. Журнал ACM, 30 (2): 323–342, 1983.
^ Jump up to: ^а ^б ^с Розье, Луи Э; Гауда, Мохамед Г. Решающий прогресс для класса взаимодействующих конечных автоматов. Остин: Техасский университет в Остине, 1983.
^ Алур, Раджив; Каннан, Сампат; Яннакакис, Михалис. «Взаимодействие иерархических конечных автоматов», Автоматы, языки и программирование. Прага: ICALP, 1999.
^ Гауда, Мохамед Дж; Розье, Луи Э. «Связь конечных автоматов с приоритетными каналами», Автоматы, языки и программирование. Антверпен: ICALP, 1984 г.

[Brand,_Zafiropulo-1] Jump up to: ^а ^б ^с ^д Д. Бранд и П. Зафиропуло. Об общении конечных автоматов. Журнал ACM, 30 (2): 323–342, 1983.

[Rosier,_Gouda-2] Jump up to: ^а ^б ^с Розье, Луи Э; Гауда, Мохамед Г. Решающий прогресс для класса взаимодействующих конечных автоматов. Остин: Техасский университет в Остине, 1983.

[3] Алур, Раджив; Каннан, Сампат; Яннакакис, Михалис. «Взаимодействие иерархических конечных автоматов», Автоматы, языки и программирование. Прага: ICALP, 1999.

[4] Гауда, Мохамед Дж; Розье, Луи Э. «Связь конечных автоматов с приоритетными каналами», Автоматы, языки и программирование. Антверпен: ICALP, 1984 г.

[1]

[2]

[3]

[4]