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 la probabilidad .
Definición
Una SDS se construye a partir de los siguientes componentes:
- Un gráfico finito Y con vértice establecido v [ Y ] = {1,2, ..., n}. Dependiendo del contexto, el gráfico puede estar 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 vértice asigna el estado de vértice i en el momento t al estado vértice en el tiempo t en base a los estados asociados a la 1-barrio de + 1 i en Y .
- Una palabra w = ( w 1 , w 2 , ..., w m ) sobre v [ Y ].
Es conveniente introducir los mapas Y -locales F i construidos a partir de las funciones de vértice por
La palabra w especifica la secuencia en la que se componen los mapas locales Y para derivar el mapa secuencial del sistema dinámico F : K n → K n como
Si la secuencia de actualización es una permutación, con frecuencia 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 un conjunto de vértices K n y aristas dirigidas ( x , F ( x )). La estructura del espacio de fase se rige por las propiedades del gráfico Y , las funciones de vértice ( f i ) i y la secuencia de actualización w . Una gran parte de la investigación de SDS busca inferir propiedades del espacio de fase basándose en la estructura de los constituyentes del sistema.
Ejemplo
Considere el caso donde Y es el gráfico con el 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, use la función booleana simétrica ni: 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 no 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 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 ni (1,0,0) = 0. Tenga en cuenta que el estado del vértice 1 en el momento 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.
Ver también
Referencias
- Henning S. Mortveit, Christian M. Reidys (2008). Introducción a los sistemas dinámicos secuenciales . Saltador. ISBN 978-0387306544.
- Problemas de existencia de predecesores y permutación para sistemas dinámicos secuenciales
- Sistemas dinámicos secuenciales genéticos