Тривиальный путь анализа соотношения множеств нитей
S
и
S
0
—
это прямое их сравнение. Если мощности множеств
S
и
S
0
равны со-
ответственно
m
и
n
, а длина последовательностей в среднем равна
k
,
то очевидно, что число операций, необходимых для сравнения, оцени-
вается экспоненциальной величиной O
(
kmn
)
, которая быстро растет
с ростом всех составляющих. Кроме того, как уже отмечалось, только
сравнительно простые процессы целесообразно задавать процессны-
ми выражениями, напрямую представляющими конечные множества
конечных нитей
S
и
S
0
. Поэтому будем полагать, что процессы
P
(
S
)
и
P
(
S
0
)
задаются каноническими процессными выражениями, позво-
ляющими описывать бесконечные множества нитей
S
и
S
0
.
Предположим, что процессы
P
(
S
)
и
P
(
S
0
)
заданы соответственно
каноническими процессными выражениями
b
(
S
)
i
,
i
= 1
, . . . , n
S
,
!
a
(
S
)
j
,
j
= 1
, . . . , p
S
, и
b
S
0
i
,
i
= 1
, . . . , n
S
0
,
!
a
S
0
j
,
j
= 1
, . . . , p
S
0
.
Рассмотрим следующий алгоритм.
Алгоритм 4
:
а) принять
r
= 1
,
s
= 0
;
б) сформировать процессное выражение
˙
b
(
s
)
r
=
b
i
1
|
b
i
2
|
. . .
|
b
i
l
из
всех состояний обоих процессов, для которых внешняя реакция
!
a
во
внешних процессных выражениях
!
a
=
b
i
j
одна и та же;
в) если имеются состояния, не вошедшие ни в одно процессное
выражение
b
(
s
)
r
, то принять
r
=
r
+ 1
и перейти к п. “б”. В противном
случае перейти к следующему п. “г”;
г) получить процессные выражения
˙
B
(
s
)
k
,
k
= 1
,
2
, . . . , r
, подста-
новкой в процессное выражение
˙
b
(
s
)
k
=
b
i
1
|
b
i
2
|
. . .
|
b
i
l
вместо каждого
состояния
b
i
j
правой части соответствующего процессного выражения
b
i
j
. Принять
j
= 1
,
A
(
s
)
j
=
?
;
д) поместить
˙
b
(
s
)
j
в множество
A
(
s
)
j
;
ж) найти все
˙
B
(
s
)
k
,
k
= 1
,
2
, . . . , r
, для которых
˙
b
(
s
)
j
∩
˙
B
(
s
)
k
6
=
?
,
k
= 1
,
2
, . . . , r
, для каждого
˙
b
(
s
)
j
2
A
(
s
)
j
;
з) если в п. “ж” для некоторого
˙
b
(
s
)
j
найдены
˙
B
(
s
)
a
, . . . ,
˙
B
(
s
)
t
та-
кие, что
˙
b
(
s
)
j
∩
˙
B
(
s
)
a
6
=
?
, . . . ,
˙
b
(
s
)
j
∩
˙
B
(
s
)
t
6
=
?
, число которых не
менее двух, и среди них существуют пары
˙
B
(
s
)
g
,
˙
B
(
s
)
h
такие, что
˙
b
(
s
)
j
∩
˙
B
(
s
)
g
=
b
m
1
?
a
m
1
|
b
m
2
?
a
m
2
|
. . .
|
b
m
k
?
a
m
k
˙
b
(
s
)
j
∩
˙
B
(
s
)
h
=
=
b
n
1
?
a
n
1
|
b
n
2
?
a
n
2
|
. . .
|
b
n
l
?
a
n
l
и хотя бы для одной пары
?
a
m
,
?
a
n
имеет
место
?
a
m
=?
a
n
, то разбить процесс
˙
b
(
s
)
j
на подпроцессы
˙
b
(
s
)
j
1
,
˙
b
(
s
)
j
2
, . . .
, в
каждый из которых входят только те состояния
b
m
=?
a
m
b
m
, b
n
=?
a
n
b
n
,
для которых нет ни одной пары
b
m
?
a
m
, b
n
?
a
n
такой, что
?
a
m
=?
a
n
.
Заменить в множестве
A
(
s
)
j
процесс
˙
b
(
s
)
j
полученными подпроцессами
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012. № 4 75
