Los sistemas dinámicos secuenciales ( SDS ) son una clase de sistemas dinámicos de grafos . Son sistemas dinámicos discretos que generalizan muchos aspectos de, por ejemplo, los autómatas celulares clásicos , y proporcionan un marco para estudiar procesos asincrónicos sobre grafos . El análisis de los SDS utiliza técnicas de combinatoria , álgebra abstracta , teoría de grafos , sistemas dinámicos y teoría de la probabilidad .
Una SDS se construye a partir de los siguientes componentes:
- Un grafo finito Y con un conjunto de vértices v[ Y ] = {1,2, ... , n}. Dependiendo del contexto, el grafo puede ser dirigido o no dirigido.
- Un estado x v para cada vértice i de Y tomado de un conjunto finito K . El estado del sistema es la n -tupla x = ( x 1 , x 2 , ... , x n ), y x [ i ] es la tupla que consiste en los estados asociados a los vértices en el vecindario 1 de i en Y (en algún orden fijo).
- Una función de vértice f i para cada vértice i . La función de vértice asigna el estado del vértice i en el momento t al estado del vértice en el momento t + 1 en función de los estados asociados al vecindario 1 de i en Y .
- Una palabra w = ( w 1 , w 2 , ... , w m ) sobre v [ Y ].
Es conveniente introducir las aplicaciones locales Y F i construidas a partir de las funciones de vértice mediante
La palabra w especifica la secuencia en la que se componen los mapas locales Y para derivar el mapa del sistema dinámico secuencial F : K n → K n como
Si la secuencia de actualización es una permutación, con frecuencia se habla de un SDS de permutación para enfatizar este punto. El espacio de fase asociado a un sistema dinámico secuencial con mapa F : K n → K n es el grafo dirigido finito con conjunto de vértices K n y aristas dirigidas ( x , F ( x )). La estructura del espacio de fase está gobernada por las propiedades del grafo Y , las funciones de vértice ( f i ) i y la secuencia de actualización w . Una gran parte de la investigación SDS busca inferir propiedades del espacio de fase basadas en la estructura de los constituyentes del sistema.
Consideremos el caso en el que Y es el grafo con vértices {1,2,3} y aristas no dirigidas {1,2}, {1,3} y {2,3} (un triángulo o círculo de 3) con estados de vértice de K = {0,1}. Para funciones de vértice utilice la función booleana simétrica nor : K 3 → K definida por nor( x , y , z ) = (1+ x )(1+ y )(1+ z ) con aritmética booleana. Por lo tanto, el único caso en el que la función nor devuelve el valor 1 es cuando todos los argumentos son 0. Elija w = (1,2,3) como secuencia de actualización. Partiendo del estado inicial del sistema (0,0,0) en el tiempo t = 0, se calcula el estado del vértice 1 en el tiempo t = 1 como nor(0,0,0) = 1. El estado del vértice 2 en el tiempo t = 1 es nor(1,0,0) = 0. Nótese que el estado del vértice 1 en el tiempo t = 1 se utiliza inmediatamente. A continuación, se obtiene el estado del vértice 3 en el tiempo t = 1 como nor(1,0,0) = 0. Esto completa la secuencia de actualización y se concluye que el mapa Nor-SDS envía el estado del sistema (0,0,0) a (1,0,0). El estado del sistema (1,0,0) se asigna a su vez a (0,1,0) mediante una aplicación del mapa 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)