Алгоритм 1
:
а) принять
i
= 0
, объявить множество
S
0
= ?
S
;
б) объявить множество
Q
0
i
=
?
;
в) если существует хотя бы одна последовательность
?
a
2
?
S
та-
кая, что
Q
0
i
R
?
a
(
Q
0
i
R
?
a
означает, что для каждой нити
?
a
1
2
Q
0
i
имеет
место
?
a
1
R
?
a
, причем если
Q
0
i
=
?
, то всегда имеет место
Q
0
i
R
?
a
), то
перейти к следующему пункту. В противном случае перейти к п. “д”;
г) считать
Q
0
i
равным
Q
0
i
∪
?
a
, а
S
0
равным
S
0
\
?
a
, и перейти к
выполнению п. “в” с новыми
Q
0
i
и
S
0
;
д) если
S
0
=
?
, то перейти к пункту е), в противном случае считать
Q
i
=
Q
0
i
, принять
i
равным
i
+ 1
и перейти к п. “б” с новым
i
;
е) отождествить полученные классы эквивалентности
Q
1
, . . . , Q
k
с
внутренними состояниями
b
1
, b
2
, . . . , b
k
процесса
P
(
S
)
. Для каждого
восприятия
?
a
2
?
A
и каждого класса эквивалентности
Q
i
найти, если
он существует, класс
Q
j
такой, что
Q
i
?
a Q
j
. Провести на графе
переходов процесса
P
(
S
)
дугу
(
b
i
, b
j
)
. Дополнить полученный граф
переходов до графа отметкой вершин внешними реакциями. Перейти
к следующему пункту;
ж) конец.
3. Оптимизация канонических процессных выражений.
Не-
трудно показать, что граф переходов процесса
P
(
S
)
, построенный по
алгоритму 1 в случае, когда функция
ϕ
(?
a
)
определена на всех ни-
тях
?
a
2
?
S
, имеет минимальное число состяний или, как говорят, он
минимален и, следовательно, минимальным будет число внутренних
и внешних канонических процессных выржений. В противном случае
это число оптимально.
Алгоритм 1 имеет существенный недостаток: он требует проверки
отношения
R
для каждой пары нитей множества
?
S
. Трудоемкость
такой проверки при числе нитей, равном
m
, и максимальной длине
нитей, равной
ζ
, оценивается
O
(
m
2
ζ
)
.
Эту оценку можно улучшить. Из определения отношения
R
непо-
средственно следует, что две нити
?
a
1
,
?
a
2
множества
?
S
тогда и толь-
ко тогда находятся в отношении
R
, когда
ϕ
(?
a
1
) =
ϕ
(?
a
2
)
. Следова-
тельно, если в одно множество включать только те нити множества
?
S
,
для каждой пары
?
a
1
,
?
a
2
которых имеет место
ϕ
(?
a
1
) =
ϕ
(?
a
2
)
, то
множество
?
S
разобьется на конечное число подмножеств (классов),
которые будем обозначать
Q
(0)
1
, Q
(0)
2
, . . . , Q
(0)
k
0
.
Пример 2
. Пусть
S
=
{
?
a
1
!
a
1
,
?
a
1
?
a
1
!
a
2
,
?
a
1
?
a
2
!
a
1
,
?
a
2
?
a
1
!
a
2
,
?
e
!
a
3
,
?
a
1
?
a
2
?
a
1
!
a
2
,
?
a
1
?
a
2
?
a
2
!
a
1
,
?
a
2
?
a
2
?
a
1
!
a
1
,
?
a
1
?
a
1
?
a
1
?
a
1
!
a
2
,
?
a
1
?
a
1
?
a
2
?
a
1
!
a
2
,
?
a
2
!
a
3
,
?
a
2
?
a
2
!
a
3
,
?
a
1
?
a
1
?
a
1
!
a
3
,
?
a
1
?
a
1
?
a
2
!
a
3
}
.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012. № 4 67
