С системно-теоретической точки зрения наиболее продвинутой теорией является теория сложности процессов, моделируемых конечными автоматами. Напомним, что каждый автомат $M$ порождает конечную полугруппу преобразований $\left(Q, \mathscr{F}^{*}\right)$, где $Q$ – пространство состояний автомата $M$, а $\mathscr{F}^{*}-$ полугруппа всех преобразований $Q$. Дадим определение сложности, используя алгебраическое понятие узлового произведения, и рассмотрим связь этого определения с автоматами и аксиомами сложности,

Определение 4.1
Назовем групповой сложностью \# ${ }_{G}(X, S)$ полугруппы $(X, S)$ наименьшее целое $n$, такое, что
\[
S \mid\left(Y_{n}, C_{m}\right) w\left(X_{n}, G_{n}\right) w \ldots w\left(Y_{1}, C_{1}\right) w\left(X_{1}, G_{1}\right) w\left(Y_{0}, C_{0}\right),
\]

где $G_{1}, \ldots, G_{m}$ – конечные простые группы, $C_{0}, \ldots, C_{k}$ конечные комбинаторные полугруппы (триггеров); «ш» обозначает операцию узлового произведения.

Следовательно, групповая сложность полугруппы $(X, S)$ это минимальное число возможных комбинаций простых групп и комбинаций комбинаторных полугрупп, составляюцих $(X, S)$. Используя теоремы декомпозиции, можно определить сложность в терминах декомпозиции фазового пространства. Например,
\[
\#_{G}(X, S)=\min \#_{G}\left\{\begin{array}{r}
T: T-\text { последовательно-параллельная } \\
\text { или каскадная декомпозиция }
\end{array}\right\} \text {. }
\]

Так как комбинаторные полугруппы представляют автоматы, а не вычисления, то основным сложным элементом является простая группа, в которой производятся такие элементарные арифметические действия, как сложение и умножение. В соответствии с теорией Крона – Роудза, возможна декомпозиция автомата в примитивные и неприводимые подавтоматы, причем решение задачи зависит от структуры компонент и длин вычислений. Поэтому и сложность зависит не только от длины цепи вычислений, но и от степени сложности каждой компоненты, входящей в цепь. Таким образом, сложность учитывает не только общее число вычислений в цепи (вычислительный аспект), но и внутреннюю сложность подавтоматов, отражаемую узловым произведением (структурный аспект). Эвристически вычислительная часть автомата представляется количеством «циклов» в машинной программе, которая вычисляет действие $\mathscr{F}^{*}$ на $Q$.

Рассмотрим взаимосвязь этого определения групповой сложности и вышеприведенных аксиом сложности.

Теорема $4.1^{1}$ )
Пусть $\theta: M_{\mathscr{E}} \rightarrow N$ (где $N$-множество неотрицательных чисел, а $M_{\mathscr{f}}$-множество всех конечных автоматов) удовлетворяет всем аксиомам сложности, причем аксиома нормализации (аксиома 5) имеет место $c$
\[
\theta\left(U_{3}\right)=0, \quad \theta\left(D_{1}\right)=0,
\]
1) Доказательство теоремы можно найти в работах, приведенных в конце главы.

где $U_{3}$-триггер с тремя состояниями, а $D_{1}$-автомат задержки ма 1 шаг. Тогда
\[
\theta(f)=\#_{o}\left(f^{s}\right)
\]

для всех $f \in M_{\mathscr{F}}\left(f^{S}\right.$ – это полугруппа автомата $f$ ).
Замечания. 1. Согласно теореме 4.1, функция групповой сложности является, по существу, единственной функцией, удовлетворяющей аксиомам сложности и данной нормализации. Для любой другой функции, удовлетворяющей аксиомам, должно выполняться неравенство
\[
\#_{G^{\prime}}(f) \leqslant \#_{G}(f) \text { для всех } f \in M_{\mathscr{F}} .
\]
2. Автомат задержки на 1 шаг, так же как $U_{3}$, является комбинаторной подгруппой, действие которой задается следующим образом:
\[
D_{1}\left(a_{1}, \ldots, a_{n}\right)=a_{n-1}, \quad D_{1}\left(a_{1}\right)=\text { null, }
\]

где $\left\{a_{n}, a_{n-1}, \ldots, a_{1}\right\}$ – любая вводимая строка.
3. $\theta(f)=0$ тогда и только тогда, когда $f$ представляет собой последовательно-параллельно соединенные автоматы $U_{3}$ и $D_{1}$.
4. Для того чтобы показать, что существуют автоматы любого уровня сложности, рассмотрим автомат
\[
\begin{aligned}
U & =\{a, b, c\}, \\
Y & =\{0,1\}, \\
Q & =\{1,2, \ldots, n\}, \\
\lambda(i, a) & =i+1(\bmod n), \quad i=1,2, \ldots, n, \\
\lambda(1, b) & =2, \\
\lambda(2, b) & =1, \\
\lambda(x, b) & =x, \quad x
eq 1,2, \\
\lambda(1, c) & =2, \\
\lambda(y, c) & =y, \quad y
eq 1, \\
\delta(q, d) & =q(\bmod 2), \quad q \in Q_{,} \quad d \in U,
\end{aligned}
\]

Используя вышеприведенные результаты и некоторые положения теории полугрупп, можно показать, что сложность этого автомата
\[
\theta(C)=n-1
\]

независимо от начального состояния $q \in Q$.

5. Нормализация $U_{3}$ и $D_{1}$ необходима в силу того, что они являются самыми простыми объектами теории: ни один из этих автоматов не выполняет вычислений и их действия полностью предсказуемы.

Нормализация напоминает известный в теории информации процесс выбора событий, имеющих нулевое информационное содержание. Автоматы $U_{3}$ и $D_{1}$ действуют регулярно, от них нельзя ожидать каких-либо сюрпризов, и поэтому их поведение не порождает информацин. Следовательно, если обнаруживаются подсистемы, которые ведут себя подобно триггерам, то они могут быть удалены без изменения структурной сложности других подсистем, несмотря на то что вычислительная сложность может уменьшиться.