Los sistemas dinámicos secuenciales ( SDS ) son una clase de sistemas dinámicos de gráficos . 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 gráficos . El análisis de SDS utiliza técnicas de combinatoria , álgebra abstracta , teoría de grafos , sistemas dinámicos y teoría de probabilidades .
Una SDS se construye a partir de los siguientes componentes:
- Un gráfico finito Y con conjunto de vértices v[ Y ] = {1,2, ..., n}. Dependiendo del contexto el gráfico 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 consta de los estados asociados a los vértices en la vecindad 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 a la vecindad 1 de i en Y.
- Una palabra w = ( w 1 , w 2 , ... , w m ) sobre v [ Y ].
Es conveniente presentar los mapas locales Y F i construidos 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, frecuentemente se habla de una 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 gráfico dirigido finito con conjunto de vértices K n y aristas dirigidas ( x , F ( x )). La estructura del espacio de fases se rige por las propiedades del gráfico Y, las funciones de vértice (fi) i y la secuencia de actualización w . Una gran parte de la investigación de SDS busca inferir las propiedades del espacio de fase basándose en la estructura de los constituyentes del sistema.
Considere el caso donde Y es el gráfico con conjunto de vértices {1,2,3} y aristas no dirigidas {1,2}, {1,3} y {2,3} (un triángulo o 3 círculos) 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 ni devuelve el valor 1 es cuando todos los argumentos son 0. Elija w = (1,2,3) como secuencia de actualización. A partir del estado inicial del sistema (0,0,0) en el momento t = 0, se calcula el estado del vértice 1 en el momento t =1 como nor(0,0,0) = 1. El estado del vértice 2 en el momento t =1 es nor(1,0,0) = 0. Tenga en cuenta que el estado del vértice 1 en el momento t =1 se usa inmediatamente. A continuación se obtiene el estado del vértice 3 en el momento 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) a su vez se asigna 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)