Последовательные динамические системы ( SDS ) являются классом графовых динамических систем . Они являются дискретными динамическими системами , которые обобщают многие аспекты, например, классических клеточных автоматов , и они обеспечивают основу для изучения асинхронных процессов на графах . Анализ SDS использует методы из комбинаторики , абстрактной алгебры , теории графов , динамических систем и теории вероятностей .
Паспорт безопасности состоит из следующих компонентов:
- Конечный граф Y с множеством вершин v[ Y ] = {1,2, ... , n}. В зависимости от контекста граф может быть направленным или ненаправленным.
- Состояние x v для каждой вершины i из Y, взятое из конечного множества K. Состояние системы — это n -кортеж x = ( x 1 , x 2 , ... , x n ), а x [ i ] — это кортеж, состоящий из состояний, связанных с вершинами в 1-окрестности i в Y (в некотором фиксированном порядке).
- Вершинная функция f i для каждой вершины i . Вершинная функция отображает состояние вершины i в момент времени t в состояние вершины в момент времени t + 1 на основе состояний, связанных с 1-окрестностью i в Y.
- Слово w = ( w 1 , w 2 , ... , w m ) над v [ Y ].
Удобно ввести Y -локальные отображения F i , построенные по вершинным функциям по формуле
Слово w определяет последовательность, в которой составляются Y -локальные отображения для вывода последовательного динамического системного отображения F : K n → K n как
Если последовательность обновления является перестановкой, часто говорят о перестановочной SDS, чтобы подчеркнуть этот момент. Фазовое пространство, связанное с последовательной динамической системой с отображением F : K n → K n , является конечным направленным графом с множеством вершин K n и направленными ребрами ( x , F ( x )). Структура фазового пространства регулируется свойствами графа Y , функциями вершин ( f i ) i и последовательностью обновления w . Большая часть исследований SDS направлена на то, чтобы вывести свойства фазового пространства на основе структуры компонентов системы.
Рассмотрим случай, когда Y — граф с множеством вершин {1,2,3} и ненаправленными ребрами {1,2}, {1,3} и {2,3} (треугольник или 3-окружность) с состояниями вершин из K = {0,1}. Для функций вершин используйте симметричную, булеву функцию nor : K 3 → K , определенную как nor( x , y , z ) = (1+ x )(1+ y )(1+ z ) с булевой арифметикой. Таким образом, единственный случай, когда функция nor возвращает значение 1, — это когда все аргументы равны 0. Выберите w = (1,2,3) в качестве последовательности обновления. Начиная с начального состояния системы (0,0,0) в момент времени t = 0, вычисляется состояние вершины 1 в момент времени t = 1 как nor(0,0,0) = 1. Состояние вершины 2 в момент времени t = 1 равно nor(1,0,0) = 0. Обратите внимание, что состояние вершины 1 в момент времени t = 1 используется немедленно. Затем получается состояние вершины 3 в момент времени t = 1 как nor(1,0,0) = 0. Это завершает последовательность обновлений, и можно сделать вывод, что карта Nor-SDS отправляет состояние системы (0,0,0) в (1,0,0). Состояние системы (1,0,0) в свою очередь отображается в (0,1,0) с помощью карты SDS.
![{\displaystyle F_{i}(x)=(x_{1},x_{2},\ldots ,x_{i-1},f_{i}(x[i]),x_{i+1},\ldots ,x_{n})\;.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b0297cda06442aa0a2bb3a1835cf94c5e8011fba)
![{\displaystyle [F_{Y},w]=F_{w(m)}\circ F_{w(m-1)}\circ \cdots \circ F_{w(2)}\circ F_{w(1)}\;.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca42ec3794afcdf858b2c72b17b1c5d18f8c90cc)