Последовательная динамическая система

Фазовое пространство последовательной динамической системы

Последовательные динамические системы ( СДС ) представляют собой класс динамических систем на графах . Это дискретные динамические системы , которые обобщают многие аспекты, например, классических клеточных автоматов , и обеспечивают основу для изучения асинхронных процессов на графах . Анализ SDS использует методы комбинаторики , абстрактной алгебры , теории графов , динамических систем и теории вероятностей .

Определение

Паспорт безопасности состоит из следующих компонентов:

• Конечный граф Y с множеством вершин v[ Y ] = {1,2, ... , n}. В зависимости от контекста граф может быть направленным или неориентированным.
• Состояние x _v для каждой вершины i графа Y, взятой из конечного множества K . Состояние системы — это n -кортеж x = ( x ₁ , x ₂ , ..., x _n ), а x [ i ] — это кортеж , состоящий из состояний, связанных с вершинами в 1-окрестности i в Y (в некотором фиксированном порядке).
• Вершинная функция f _i для каждой вершины i . Функция вершины отображает состояние вершины i в момент времени t в состояние вершины в момент времени t + 1 на основе состояний, связанных с 1-окрестностью вершины i в Y .
• Слово w = ( w ₁ , w ₂ , ... , w _m ) над v [ Y ].

Удобно ввести Y -локальные отображения F _i, построенные из вершинных функций по формуле

$F_{i}(x)=(x_{1},x_{2},\ldots ,x_{i-1},f_{i}(x[i]),x_{i+1},\ldots ,x_{n})\;.$

Слово w определяет последовательность, в которой Y составляются -локальные карты для получения последовательной карты динамической системы F : K. ^н → К ^н как

$[F_{Y},w]=F_{w(m)}\circ F_{w(m-1)}\circ \cdots \circ F_{w(2)}\circ F_{w(1)}\;.$

Если последовательность обновления представляет собой перестановку, часто говорят о SDS перестановки, чтобы подчеркнуть этот момент. Фазовое пространство , связанное с последовательной динамической системой с отображением F : K ^н → К ^н — конечный ориентированный граф с множеством вершин K ^н и направленные ребра ( x , F ( x )). Структура фазового пространства определяется свойствами графа Y , вершинными функциями ( fi ₎ i _w последовательностью обновления и . Большая часть исследований SDS направлена ​​​​на вывод свойств фазового пространства на основе структуры компонентов системы.

Пример

Рассмотрим случай, когда Y — граф с множеством вершин {1,2,3} и неориентированными ребрами {1,2}, {1,3} и {2,3} (треугольник или 3-окружность) с состояниями вершин из К = {0,1}. Для вершинных функций используйте симметричную логическую функцию nor : K ³ → K определяется формулой nor( x , y , z ) = (1+ x )(1+ y )(1+ z ) с булевой арифметикой. Таким образом, единственный случай, когда функция не возвращает значение 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.

См. также

• Графовая динамическая система
• Логическая сеть
• Сеть регулирования генов
• Динамическая байесовская сеть
• сеть Петри

Ссылки

• Хеннинг С. Мортвейт, Кристиан М. Рейдис (2008). Введение в последовательные динамические системы . Спрингер. ISBN  978-0387306544 .
• Проблемы существования предшественников и перестановок для последовательных динамических систем
• Генетические последовательные динамические системы