Блокировочное соединение автоматов

Блокиро́вочное соедине́ние, или блокиро́вка семейства $\textstyle N$ конечных автоматов ${\mathcal A_k}~ (k = 1, 2, \ldots, N)$, определяется заданием множества $\textstyle N$ предикатов блокировки переходов этих автоматов:

$\chi_k: S_1 \times S_2 \times \ldots \times S_{k-1} \times \ldots \times S_{k+1} \times \ldots \times S_N \to \{0, 1\} ,~ k \in [1,N]$ ,

где $\textstyle S_k$ — множество состояний автомата $\mathcal A_k$. Предикаты блокировки ${\chi_k},~ k \in [1,N]$, выражают взаимные ограничения на переходы автоматов, связанных блокировочным соединением.

Если $\chi_k(s_1, s_2, \ldots s_{k-1}, s_{k+1}, \ldots s_N) = 0$, где $s_j \in S_j~ (j = 1, 2, \ldots N)$, то автомат $\mathcal A_k$ «заблокирован» набором состояний $(s_1, s_2, \ldots s_{k-1}, s_{k+1}, \ldots s_N)$ остальных автоматов: все переходы автомата $\mathcal A_k$ «запрещены», любой входной сигнал автомата $\mathcal A_k$ заменяется тождественным входным сигналом.

Если $\chi_k(s_1, s_2, \ldots s_{k-1}, s_{k+1}, \ldots s_N) = 1$, то переходы автомата $\mathcal A_k$ не зависят от состояний других автоматов: все переходы автомата $\mathcal A_k$ «разрешены», автомат $\mathcal A_k$ ведет себя в соответствии с собственными функциями переходов и выходов.

Разрешающие и запрещающие состояния

Если $\textstyle N=2$, то блокировочное соединение $\mathcal A^\diamond = \mathcal A_1 \diamond \mathcal A_2$ автоматов $\mathcal A_1$ и $\mathcal A_2$ определяется парой предикатов блокировки $\chi_1: S_2 \to \{0, 1\}$ и $\chi_2: S_1 \to \{0, 1\}$. Обозначим:

$\textstyle F_1$ — множество всех таких $s_1 \in S_1$, что $\textstyle \chi_2(s_1) = 0$;

$\textstyle T_1$ — множество всех таких $s_1 \in S_1$, что $\textstyle \chi_2(s_1) = 1$;

$\textstyle F_2$ — множество всех таких $s_2 \in S_2$, что $\textstyle \chi_1(s_2) = 0$;

$\textstyle T_2$ — множество всех таких $s_2 \in S_2$, что $\textstyle \chi_1(s_2) = 1$.

Элементы множеств $\textstyle T_1$ и $\textstyle T_2$ называются разрешающими состояниями автоматов $\mathcal A_1$ и $\mathcal A_2$ соответственно, элементы множеств $\textstyle F_1$ и $\textstyle F_2$ — запрещающими состояниями автоматов $\mathcal A_1$ и $\mathcal A_2$.

Если один из двух автоматов $\mathcal A_1$ или $\mathcal A_2$ находится в разрешающем состоянии, то другой работает как бы «сам по себе», как предписывают его собственные функции переходов и выходов. Если же один автомат находится в запрещающем состоянии, то работа другого автомата полностью блокируется: каждый его входной сигнал заменяется тождественным.

Односторонние и взаимные блокировки

Если одно из множеств запрещающих состояний $\textstyle F_1$ или $\textstyle F_2$ пусто, то блокировка $\mathcal A^\diamond = \mathcal A_1 \diamond \mathcal A_2$ называется односторонней. В противном случае – двусторонней или взаимной. При односторонней блокировке работа только одного из соединяемых автоматов зависит от состояния другого.

Односторонняя блокировка есть частный случай каскадного соединения автоматов. Взаимная блокировка не является частным случаем каскадного соединения.

Односторонняя блокировка автомата $\mathcal A_1$ автоматом $\mathcal A_2$ называется максимальной, если множество $\textstyle T_2$ содержит ровно один элемент. При максимальной односторонней блокировке автомат $\mathcal A_1$ работает (в соответствии со своими функциями переходов и выходов) только при одном состоянии автомата $\mathcal A_2$. Все остальные состояния автомата $\mathcal A_2$ являются блокирующими для автомата $\mathcal A_1$.

Автомат группы сильно связен точно тогда, когда его группа транзитивна. Группа автомата максимальной односторонней блокировки перестановочного автомата $\mathcal A_1$ сильно связным перестановочным автоматом $\mathcal A_2$ есть подстановочное сплетение групп автоматов $\mathcal A_1$ и $\mathcal A_2$. Обратно, подстановочное сплетение конечной группы $\textstyle G_1$ и транзитивной конечной группы $\textstyle G_2$ изоморфно группе максимальной односторонней блокировки перестановочного автомата $\mathcal A_1$, группа которого есть $\textstyle G_1$, перестановочным автоматом $\mathcal A_2$, группа которого есть $\textstyle G_2$.

Взаимная блокировка автоматов $\mathcal A_1$ и $\mathcal A_2$ называется максимальной, если их множества разрешающих состояний $\textstyle T_1$ и $\textstyle T_2$ содержат ровно по одному элементу. Группа максимальной взаимной блокировки двух сильно связных перестановочных автоматов $\mathcal A_1$ и $\mathcal A_2$, число состояний которых равно $\textstyle K+1$ и $\textstyle N+1$ соответственно, есть либо симметрическая группа $\textstyle S_{K+N+1}$, либо знакопеременная группа $\textstyle A_{K+N+1}$. Второй случай имеет место тогда и только тогда, когда группы обоих автоматов $\mathcal A_1$ и $\mathcal A_2$ содержат только четные подстановки.

Литература

• Головинский И. А. Блокировки автоматов групп. I. Односторонние блокировки. // Известия РАН. Теория и системы управления, 2009, № 1, с. 49-73. Англ. перевод: Golovinskii I. A. Blocking of group automata. I. One-sided interlocking. // Journal of Computer and Systems Sciences International, 2009, vol. 48, No 1, p. 45-69.
• Головинский И. А. Блокировки автоматов групп. II. Взаимные блокировки. // Известия РАН. Теория и системы управления, 2009, № 2, с. 72-83. Англ. перевод: Golovinskii I. A. Blocking of group automata. II. Mutual interlocking. // Journal of Computer and Systems Sciences International, 2009, vol. 48, No 2, p. 231-242.

Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей.