next up previous contents index
Next: Diagrama de de Bruijn Up: Introducción al Espacio de Previous: Homomorfismos   Contenido   Indice

Corrimientos de Tipo Finito

Se ha visto que en un espacio de corrimiento $ \mathcal{C}$, $ \sigma$ mapea el espacio a si mismo, esto se conoce como el sistema dinámico de corrimiento. En un autómata celular lineal, tenemos que el espacio de configuraciones $ \mathcal{C}$ está compuesto por todas las secuencias infinitas de estados posibles, donde $ K$ representan el conjunto finito de estados. Llamaremos el $ K$-corrimiento completo a todo el conjunto de posibles secuencias infinitas que se puedan generar con $ K$, esto es:

\begin{displaymath}\begin{array}{r} K\mbox{{\it -corrimiento completo} }=K^\math...
...C}_{[i]} \in K \mbox{ } \forall i \in \mathbb{Z}\}. \end{array}\end{displaymath} (33)

entonces, cada configuración de estados $ \mathrm{C}$ pertenece a $ K^\mathbb{Z}$.

Un corrimiento de tipo finito [Boy93] es una restricción del $ K$-corrimiento completo, en donde existe un conjunto finito $ \mathfrak{P}$ de secuencias de estados prohibidas, es decir, ningún elemento de $ \mathfrak{P}$ puede aparecer en las configuraciones pertenecientes al corrimiento de tipo finito. Definamos a $ \mathcal{C}_{\begin{picture}(5,5)(0,0) \put(0,0){\mbox{\tiny $\mathfrak{P}$}} \put(0,0){\mbox{\small $\times$}}
\end{picture}}$ como el corrimiento de tipo finito formado por configuraciones de estados que no contienen ninguna secuencia en $ \mathfrak{P}$, con esto se tiene que:

$\displaystyle \mathcal{C}_{\begin{picture}(5,5)(0,0) \put(0,0){\mbox{\tiny$\mathfrak{P}$}} \put(0,0){\mbox{\small$\times$}} \end{picture}}\subseteq \mathcal{C}.$ (34)

En el ámbito de un autómata celular lineal, un corri-miento de tipo finito $ \mathcal{C}_{\begin{picture}(5,5)(0,0) \put(0,0){\mbox{\tiny $\mathfrak{P}$}} \put(0,0){\mbox{\small $\times$}}
\end{picture}}$ es el conjunto de todas las posibles configuraciones donde $ \mathfrak{P}$ son las secuencias de estados base del Jardín del Edén de dicho autómata, con lo que $ \mathcal{C}_{\begin{picture}(5,5)(0,0) \put(0,0){\mbox{\tiny $\mathfrak{P}$}} \put(0,0){\mbox{\small $\times$}}
\end{picture}}$ contiene solamente aquellas configuraciones que son posibles de generar con la regla de evolución $ \phi$.


next up previous contents index
Next: Diagrama de de Bruijn Up: Introducción al Espacio de Previous: Homomorfismos   Contenido   Indice
ice 2001-08-30