Взаимодействующие автоматы

Определение 13.

Взаимодействующим автоматом будем называть шестерку ( S, s0, X, Y, E, Q ), где

S - множество состояний,
s0
S - начальное состояние,
X - множество стимулов,
Y - множество реакций,
E
S x ( X
Y
{τ} ) x S - множество переходов, которые мы будем называть
- посылающими, если второй элемент перехода является стимулом,
- принимающими, если второй элемент перехода является реакцией,
- внутренним, если второй элемент перехода является τ;
Q
S - множество заключительных состояний.

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

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

Заметим, что множества стимулов и реакций могут пересекаться (X

Y ≠ Ø), и поэтому в определении множества переходов используется операция дизъюнктивного объединения. Для обозначения того факта, что сообщение является стимулом мы будем использовать символ !, помещаемый следом за элементом множества X (например, x!), а для обозначения принадлежности сообщения к множеству реакций будет использоваться символ ?: (например, y?).

Конечная последовательность переходов ( e1, e2, …, en ) взаимодействующего автомата A = ( S, s0, X, Y, E, Q ) называется путем, если для каждого i = 1, …, n-1 постсостояние перехода ei совпадает с пресостоянием перехода ei+1. При этом мы будем говорить, что путь ведет из пресостояния перехода e1 в постсостояние перехода en.

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

Путь ( e1, e2, …, en ) взаимодействующего автомата A = ( S, s0, X, Y, E, Q ) называется функционированием, если пресостоянием перехода e1 является начальное состояние s0, а постсостояние перехода en принадлежит множеству конечных состояний Q.

Предположим, что взаимодействующий автомат A = ( S, s0, X, Y, E, Q ) входит в состав распределенного взаимодействующего автоматов DA. Переходы автомата A ( s1, m, s2 )

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

Функционированием распределенного взаимодействующего автомата DA называется тройка ( E,

, μ ), где

E - набор функционирований { ( ei,1, ei,2, …, ei,n(i) ) } всех взаимодействующих автоматов, входящих в DA;
- частичный порядок на множестве всех переходов { ei,j }i, j=1,…,n(i) набора E;
μ : { ei,j }
{ ei,j } - отображение на этом же множестве переходов;

при условии, что E,

и μ удовлетворяют следующим ограничениям:

областью определения μ является множество всех принимающих переходов ei,j = ( s1, m?, s2 ) автомата A, сообщение m которых сокрыто в некоторой системе взаимодействующих автоматов SA, входящей в состав DA;
для каждого такого перехода ei,j = ( s1, m?, s2 ) значением μ(ei,j) является посылающий переход ei',j' = ( s'1, m!, s'2 ) автомата A', входящего в состав той же системы взаимодействующих автоматов SA, но не совпадающего с A (A ≠ A');
частичный порядок
сохраняет порядок переходов, относящихся к функционированию одного взаимодействующего автомата, то есть

ei,j, ei',j'
{ ei,j } (i = i')
(j < j')
ei,j
ei',j';
переходы, связанные отношением μ, являются неразличимыми относительно частичного порядка
, то есть

ei,j, ei',j'
{ ei,j } ei',j' = μ(ei,j)

e
{ ei,j } ( (e
ei,j)
(e
ei',j') )
( (ei,j
e)
(e i',j'
e) ).

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

Содержание раздела