Sesión Matemática Discreta y Teoría de JuegosDescripción del Conjunto Límite de una familia de Autómatas Celulares Permutacionales
Luca D'Amico
Universidad Nacional de Salta, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
En el marco de la teoría de la dinámica de los autómatas celulares unidimensionales, resulta interesante considerar familias de autómatas que alcanzan el conjunto límite en una cantidad finita de iteraciones. Algunos casos fueron estudiados en [1], [3] y [7].
A partir de un código prefijo \(\cal C\) que permite la codificación de todo el full shift \(\cal A^{\mathbb N}\), se define el Automata Celular Permutacional Elector asociado \(\mathbb{E}_{\cal C}\) por: \(\mathbb{E}_{\cal C}\left( x \right)_{i}=\sigma^{l(i)}{\left( x\right)}_i\), donde \(\sigma\) es la funcion de \(\cal A^{\mathbb{N}}\) a \(\cal A^{\mathbb{N}}\) definida por \(\sigma(x)_i=x_{i+1}\), y \(l(i)\) es la longitud del elemento de \(\cal C\) que comienza en la posición \(i\) del punto.
Si consideramos el código prefijo \({\cal C}=\{000,001,010,011,1000,1001,101,11\}\), y \(\mathbb{E}_{{\cal C}}\) el Automata Celular Permutacional Elector asociado, resulta que \(\mathbb{E}_{{\cal C}}\) alcanza el conjunto límite en una cantidad finita de iteraciones en sus puntos finalmente periódicos.
Es decir, demostramos que para todo \(x\in \cal A^{\mathbb{N}}\), \(\sigma-\)periódico de periodo mínimo \(n\), existe \(j\leq n\in \mathbb{N}\) tal que
\[\mathbb{E}_{{\cal C}}^{j}(x)=\sigma^{k}(\mathbb{E}_{{\cal C}}^{j-1}(x)), k \in \{2,3\} \tag{1} \label{sigmalpnUMA}\]
En particular, a partir de los parámetros del código que determinan el autómata, logramos entender cuando ocurre que \(k=2\) o \(k=3\).
Además, demostramos que el conjunto límite (en sus puntos finalmente periódicos) de todos los autómatas celulares electores que cumplen \((1)\) es
\[\Lambda_{\mathbb{P}}(E) = \bigcup_{k \in \mathbb{N}} (\bigcap_{\{p^k_n\}_n} E_{\mathcal{C}}^{p^k_n}(\mathbb{P}_{p^k_n})), \tag{2} \label{EPOPUMA}\]
siendo \(\{p^k_n\}_n\) una sucesión de números naturales para todo \(k \in \mathbb{N}\).
Finalmente, a partir de \((2)\) y un resultado clásico sobre \(\omega-\)límites de conjuntos ([5]), demostramos que el conjunto límite para todos los autómatas celulares electores que cumplen \((1)\) es
\[\Lambda(E) = \bigcup_{k \in \mathbb{N}} (\bigcap_{\{p^k_n\}_n} E_{\mathcal{C}}^{p^k_n}(\mathbb{P}_{p^k_n})) \tag{3} \label{COREPOPUMA}\]
Trabajo en conjunto con: Camilo Alberto Jadur (Universidad Nacional de Salta) y Diego Luis Alberto (Universidad Nacional de Salta).
Referencias
[1] F. Blanchard, G. Hansel. Systemes codes. 1986, Theoret. Comput. Sci. 44, no. 1, p. 17-49.
[2] G. Hedlund. Endomorphisms and automorphisms of the shift dynamical systems. 1969, Math. Syst. Theory 4, 3, p. 320-375.
[3] Jadur, C. Yazlle, J. On the dynamics of autómata celular induced from a prefix code. Advances in Applied Mathematics, Elsevier.2007 vol.38 n38. p27-53. issn 0196-8858.
[4] Kurka, P. Languages, Equicontinuity and Attractors in Cellular Automata. 1997, Ergodic Theory And Dynamical Systems 17, p. 417-433.
[5] Kurka, P. Topological and Symbolic Dynamics. 2003, Cours Specialises 11, Societe Mathematique de France.
[6] Lind, D. Marcus, B. Symbolic Dynamics and Coding. 1995, Cambridge University Press.
[7] Alberto, D. Sensitivity of Cellular Automata: The Case of Variable Length Shifts. Journal of Cellular Automata 13, 429–440 (2017).