Autómatas celulares sobre grupos y un problema del rank

Resumen

En los últimos años la teoría matemática de los autómatas celulares ha sido enormemente enriquecida a partir de sus conexiones con la teoría de grupos, la topología, teoría de códigos, entre otras áreas; el conjunto de células y el conjunto de estados son equipados con estructuras matemáticas, y nuevas preguntas surgen. En este artículo hacemos una invitación a la teoría de los autómatas celulares sobre grupos, más específicamente desde la perspectiva de los grupos finitos y del concepto de rank de un semigrupo finito. En la última sección presentamos algunos resultados muy elementales acerca de cotas superiores para el rank del grupo de autómatas celulares invertibles, cuando éstos están definidos sobre ciertas familias de grupos finitos. Dichos resultados forman parte del trabajo de tesis que realizó el autor.

Introducción

Los autómatas celulares fueron introducidos por John Von Neumann en los años 1950's, quien los usó para describir modelos teóricos de máquinas autorreplicantes [Neu66]. Y desde entonces, han sido estudiados intensamente desde distintos puntos de vista, debido a la multitud de aplicaciones y a su riqueza matemática.

En el sentido clásico, un autómata celular es una transformación $\tau\colon A^{\mathbb{Z}^{d}}\rightarrow A^{\mathbb{Z}^{d}}$ tal que:

• $\mathbb{Z}^{d}$ con $d \in \mathbb{N}-\{0\}$ (la dimensión) es el universo (conjunto de células, una retícula uniforme).
• $A$ es un conjunto finito (no vacío), el conjunto de estados.
• $A^{\mathbb{Z}^{d}}$ es el conjunto de configuraciones, i.e. mapeos $\mathbf{c}\colon\mathbb{Z}^{d} \rightarrow A$.
• Para toda $\mathbf{c}\in A^{\mathbb{Z}^d}$, el estado de $v\in \mathbb{Z}^d$ en $\tau(\mathbf{c})$ está determinado por una regla local fija que solo depende de una vecindad finita $v+S\subseteq \mathbb{Z}^d$.

El Juego de la Vida es por mucho el autómata celular más conocido. Fue inventado por el matemático británico John. H. Conway. Este autómata celular fue descrito por primera vez por Martin Gardner [Gar70] en la edición de octubre de 1970 del ``Scientific American". Consideremos una retícula ortogonal bidimensional infinita con celdas cuadradas, cada una de las cuales está en uno de los dos posibles estados: viva (negro) o muerta (blanco). Toda célula $c$ interactúa con sus ocho células vecinas a cada paso en el tiempo de acuerdo a las siguientes reglas de evolución:

• (Nacimiento) Una célula muerta al tiempo $t$ cobrará vida al tiempo $t+1$ si y sólo si tres de sus vecinas están vivas en el tiempo $t$.
  

• (Supervivencia) Una célula que está viva el tiempo $t$ permanecerá viva al tiempo $t+1$ si y sólo si tiene dos o tres vecinas vivas al tiempo $t$.
  

• (Muerte por soledad) Una célula viva que tiene a lo más una vecina viva en el tiempo $t$ estará muerta al tiempo $t+1$.
  

• (Muerte por sobrepoblación) Una célula viva al tiempo $t$ y que tiene cuatro o más vecinas vivas en el tiempo $t$, estará muerta al tiempo $t+1$.
  

Estas sencillas reglas pueden dar lugar a dinámicas complejas. Incluso desde el punto de vista de la teoría de la computación, es importante debido a que tiene el poder de una máquina universal de Turing, es decir, cualquier cosa que pueda ser calculado algorítmicamente puede ser calculado usando el Juego de la Vida.

Autómatas celulares sobre grupos

Consideremos un grupo $G$, un conjunto no vacío $A$ y el conjunto $A^{G}$ de mapeos de $G$ en $A$: $$A^G=\prod_{g\in G}A= \{x\colon G\rightarrow A\}.$$ El conjunto $A$ es llamado el alfabeto. Los elementos de $A$ son llamados las letras, o estados. El grupo $G$ es llamado el universo: el conjunto de células. El conjunto $A^{G}$ es llamado el espacio de configuraciones. Note que una configuración consiste en un mapeo que asigna estados a cada célula en el grupo.

Si equipamos cada factor $A$ de $A^G$ con la topología discreta (todos los subconjuntos de $A$ son abiertos) y $A^G$ con la topología producto asociada, esta última es llamada la topología prodiscreta.

Dados $x\in A^{G}$ y $g\in G$ podemos definir la acción de traslación del grupo $G$ en $A^G$ mediante $$g\cdot x(h)=x(g^{-1}h), \ \ \forall h\in G.$$

En el sentido clásico, la definición de autómata celular considera $G=\mathbb{Z}^d$, para $d\geq 1$ y $A$ un conjunto finito. Para ilustrar los elementos de la definición, veamos nuevamente el juego de la vida.

Al conjunto de los autómatas celulares sobre $\mathbf{A^{G}}$ le denotamos por $\CA(G;A)$. Es decir,

\[ \CA(G;A) = \{ \tau \colon A^G \to A^G : \tau \text{ es un autómata celular} \}. \]

Del teorema anterior se sigue que el conjunto $\CA\left(G;A\right)$ es un moniode bajo la composición de mapeos.

Autómatas Celulares sobre Grupos Finitos

Aunque algunos resultados sobre monoides de autómatas celulares han aparecido antes en la literatura, la estructura algebraica de $\CA\left(G;A\right)$ sigue siendo básicamente desconocida. En particular, el estudio de $\CA\left(G;A\right)$, cuando $G$ y $A$ son ambos finitos, generalmente había sido ignorado, tal vez porque algunas de las preguntas clásicas se responden trivialmente (por ejemplo, los teoremas del Jardín del Edén se vuelven triviales). Sin embargo, en este contexto surgen muchas preguntas nuevas, típicas de la teoría de semigrupos.

El famoso teorema de Curtis-Hedlund caracteriza a los autómatas celulares con alfabetos finitos.

Por el teorema de Curtis-Hedlum, un mapeo $\tau \colon A^G \to A^G$ es un autómata celular si y sólo si $\tau$ es $G$-equivariante y continuo en la topología prodiscreta de $A^G$. Ahora bien, si tanto $A$ como $G$ son finitos, todo mapeo $\tau \colon A^G \to A^G$ es continuo, así que:

$$\CA\left(G;A\right)=\{\tau \colon A^G \to A^G:\tau\text{ es $G$-equivariante}\}.$$

En otras palabras $\CA\left(G ; A\right)$ es el monoide de endomorfismos del $G$-conjunto $A^G$. Este resultado nos permite estudiar $\CA\left(G ; A\right)$ desde una perspectiva puramente algebraica.

El grupo de unidades del monoide $\CA\left(G ; A\right)$ es denotado por $\ICA(G;A)$, en otras palabras $\ICA(G;A)$ es el grupo de los autómatas celulares invertibles: $$\ICA(G;A):= \{ \tau \in \CA(G;A): \exists \tau ^{-1} \in \CA(G;A) \text{ tal que $\tau \tau^{-1} =\tau^{-1}\tau=\mathrm{id}$}\}$$

Con la finalidad de introducir el teorema de estructura del grupo $\ICA(G;A)$ recordemos algunos conceptos y resultados clásicos.

El estabilizador y la $G$-órbita de una configuración $x\in A^G$ son definidas respectivamente, mediante $$G_x:=\{ g\in G: g\cdot x=x\}\quad\text{y}\quad Gx=\{g\cdot x : g\in G\},$$ los estabilizadores son subgrupos de $G$, mientras que el conjunto $\mathcal {O}(G;A)$ de $G$-órbitas constituye una partición del espacio de configuraciones $A^G$. Observe que por $G$-equivarianza un autómata celular mapea órbitas en órbitas preservando así la partición $\mathcal {O}(G;A)$ de $A^G$.

El siguiente resultado se conoce como el teorema órbita-estabilizador

Dos subgrupos $H_1$ y $H_2$ de $G$ son conjugados en $G$ si si existe $g\in G$ tal que $g^{-1}H_1g=H_2$. Esto define una relación de equivalencia en los subgrupos de $G$. Denotemos por $[H]$ la clase de conjugación de $H\leq G$. Un subgrupo $H\leq G$ es normal si $[H]=\{H\}$. Sea $N_G(H):=\{g\in G: H=g^{-1}Hg\}\leq G$ el normalizador de $H$ en $G$. Note que $H$ es siempre normal en $N_G(H)$. Denotemos por $r(G)$ el número de clases de conjugación de subgrupos de $G$, y por $r_i(G)$ el número de clases de conjugación $[H]$ tales que $H$ tiene índice $i$ en $G$.

El siguiente resultado arroja un poco de luz respecto a la estructura del grupo de autómatas celulares invertibles.

Sea $H$ un subgrupo de $G$ y $[H]$ su clase de conjugación. Definimos $$B_{[H]}(G;A):=\{x\in A^G :[G_x]=[H]\}.$$

Note que $B_{[H]}(G;A)$ es unión de $G\text{-órbitas}$ y, por el Teorema 3.2, todas las $G\text{-órbitas}$ contenidas en $B_{[H]}(G;A)$ tienen la misma cardinalidad.

Definimos $$\alpha_{[H]}(G;A):=\left|\{O\in \mathcal {O}(G;A):O\subseteq B_{[H]}(G;A)\}\right |.$$ Si $r$ es el número de las distintas clases de conjugación de subgrupos de $G$, observe que $$\mathcal{B}:=\{B_{[H]}(G;A):H\leq G\}$$ es una partición de $A^G$ en $r$ bloques.

Recapitulando, podemos organizar el espacio de configuraciones de la siguiente manera: por cada clase de conjugación $[H]$ de subgrupos de $G$, hay una ``caja'' $B_{[H]}(G;A)$ que contiene configuraciones organizadas en $\alpha_{[H]}(G;A)$ órbitas del mismo tamaño. Con esto en mente, vemos que esencialmente los elementos del grupo $\ICA(G;A)$ necesariamente mapean configuraciones en una caja en configuraciones dentro de esa misma caja preservando la partición uniforme que definen la órbitas dentro de ella. Esto motiva, grosso modo, el teorema de estructura del grupo $\ICA(G;A)$, y antes de enunciarlo recordemos brevemente el concepto de producto corona.

Para un entero $\alpha\geq 2$ y cualquier grupo $C$, el producto corona de $C$ por $S_{\alpha}$ es el conjunto $$C\wr S_\alpha :=\{(v;\phi): v\in C^{\alpha}, \phi\in S_{\alpha}\}$$ equipado con la operación $$(v;\phi)\cdot(w;\psi)=(vw^{\phi};\phi\psi),\text{ para cualesquiera $v,w\in C^{\alpha}$, $\phi$, $\psi\in S_{\alpha}$,}$$ donde $\phi$ actúa en $w$ permutanto sus coordenadas: $$w^{\phi}=(w_1,ww_2,\dots,w_\alpha)^{\phi}:=(w_{\phi(1)},w_{\phi(2)},\dots,w_{\phi(\alpha)}).$$ De hecho, como puede observarse de las definiciones anteriores, $C\wr S_\alpha$ es igual al producto semidirecto externo $C^{\alpha}\rtimes_\rho S_\alpha$ donde $\rho\colon S_\alpha \rightarrow \AUT(C^\alpha)$ está dado por $\varphi(\phi(w)):=w^{\phi}$, $\rho\in S_\alpha$.

Los siguientes resultados fueron desarrollados por los investigadores Alonso Castillo Ramírez y Maximilien Gadouleau, el lector interesado puede consultar los detalles de esta construcción en [CG17].

Para poder aplicar el teorema anterior necesitamos conocer el valor de los $\alpha_{[H]}(G;A)$, para cada $H\leq G$. Este número se puede dar en términos de la función de Möbius de un conjunto finito parcialmente ordenado $(P,\leq)$, la cual es un mapeo $\mu\colon P\times P\rightarrow \mathbb{Z}$ definido inductivamente por las siguientes ecuaciones:

\begin{align*} \mu(a,a)=1, &\forall a\in P,\\ \mu(a,b)=0, &\forall a \mayorque b,\\ \sum\limits_{a\leq c\leq b}^{} \mu(a,c)=0, &\forall a \menorque b. \end{align*}

Note que si $L(G)$ es el conjunto de subgrupos de $G$ y $\left(L(G),\subseteq\right)$ el retículo de subgrupos de $G$, entonces la función de Möbius $\mu\colon L(G)\times L(G)\rightarrow \mathbb{Z}$ de $\left(L(G),\subseteq\right)$, satisface: $\mu(H,H)=1$ para cada $H\leq G$, y $\mu(H,K)=-1$ si $H$ es un subgrupo maximal de $K\leq G$.

El concepto de rank

Dentro de la matemática, una de las palabras que más interpretaciones tiene según el área de estudio es «rango». En este sentido, hemos decidido referirnos como rank en lugar de rango para darle un poco más de identidad al concepto. El rank de un semigrupo finito $S$, denotado por $\Rank(S)$ es la cardinalidad mínima de un conjunto generador, es decir,

$$\Rank(S):=\min\{|H|:H\subseteq S, \langle H\rangle=S\}.$$

Dado un conjunto finito $X$ con $|X|=n$, se tienen los siguientes tres conjuntos notables

\begin{align*} \Tran(X)&:=\{f\colon X\longrightarrow X \} \\ S_n & :=\{f\colon X\longrightarrow X: f \text{ es biyectiva}\} \\ \Sing(X)& :=\{f\colon X\longrightarrow X: f \text{ no es biyectiva}\} \end{align*}

Observe que bajo la composición de mapeos: $\Tran(X)$ es un monoide, $S_n$ es un grupo (el grupo simétrico en $n$ elementos) y $\Sing(X)$ es un semigrupo.

Pues bien, una cuestión típica en la teoría de semigrupos finitos, es la determinación del rank de un semigrupo finito dado. A continuación, se muestran algunos resultados conocidos:

• $\Rank(\Tran(X))=\Rank(\Sym(X))+1=3$.
• $\Rank(\Sing(X))=\binom{m}{2}$ (Gomes-Howie '87, [GH87]).
• $\Rank(\{f\in \Tran(X):|f(X)|\leq r \})= S(m,r)$, el número de Stirling de segunda especie (Howie, J., McFadden '90, [HM90]).
• $\Rank(\Tran(X, \mathcal{O}))=4$, donde $\mathcal{O}$ es una partición uniforme de $X$ (Araújo-Schneider '09, [AJS09]).
• $\Rank(\Tran(X, \mathcal{O}))$, donde $\mathcal{O}$ es una partición arbitraria de $X$, se conoce, pero depende de la partición. (Araújo-Bentz-Mitchell-Schneider '15, [Ara+09]).

El rank de un monoide finito se puede desglosar de la siguiente manera.

Aquí la expresión $\Rank(M:U)$ denota el rank relativo de $U$ en $M$. En general, para un monoide finito $M$ y $U\subseteq M$, el rank relativo de $U$ en $M$, es la cardinalidad mínima de un subconjunto $V\subseteq M$ tal que $\langle U \cup V\rangle=M$.

Naturalmente el concepto puede aplicarse también a grupos, y la siguiente tabla resume algunas observaciones al respecto.

Ranks de Grupos Notables
Grupo	Rank	Genereadores
$\mathbb{Z}_n$	1	$\langle1 \rangle$
$\Tran(n),\quad n \mayorque 2$	3	$\langle (1,2),(1,2,3,\dots,n), (1\rightarrow 2) \rangle$
$S_n,\quad n \mayorque 2$	2	$\langle(1,2),(1,2,3,\dots,n)\rangle$
$\mathbb{D}_{2n},\quad n \mayorque 1$	2	$\langle\sigma, \rho\rangle$
$Q_8$	2	$\langle i,j\rangle$
$\mathbb{Z}_m\times \mathbb{Z}_n,\quad \mathrm{mcd}(m,n)\neq1$	2	$\langle (1,0),(0,1)\rangle$

Observe que por el teoema de Cayley el rank no es bien comportado bajo subgrupos, en otras palabras $H\leq G$ no implica $\Rank(H)\leq\Rank(G)$. Sin embargo, podemos considerar las siguientes herramientas elementales para acotar el rank de un grupo.

Por otro lado, la longitud $l(G)$ de un grupo finito $G$, es la longitud $l$ de la cadena $$\{e\}=H_0 \menorque H_1 \menorque \cdots \menorque H_l=G$$

más extensa de subgrupos de $G$.

En este sentido, las siguientes relaciones se cumplen.

Finalmente, el resultado que enunciamos a continuación es simplemente excepcional. Es presentado por primera vez en el artículo [MP87] de Annabelle McIver y Peter M. Neumann. La demostración actual de este teorema utiliza la clasificación de los grupos simples finitos y por lo tanto, no es elemental. El lector interesado puede consultar un artículo [CST89] de Peter Cameron para ver un bosquejo de la demostración. Por desgracia la demostración no es constructiva y son problemas abiertos tanto la elaboración una demostración elemental como la construcción de un algoritmo eficiente para generar el conjunto generador minimal en cuestión.

Rank del grupo $\ICA(G;A)$

Recordemos que el conjunto $\CA(G;A)$ de todos los autómatas celulares sobre un grupo finito $G$ y con alfabeto finito $A$, forma un monoide bajo la composición de mapeos, mientras que el conjunto $\ICA(G;A)$, de unidades de este monoide, constituye naturalmente un grupo. Luego, es factible plantear el siguiente objetivo:

Problema: Dado un grupo finito $G$ y un conjunto finito $A$, determinar $\Rank\left(\CA(G;A)\right)$.

Este problema ha sido abordado en [CG16], donde se presentan resultados cuando $G$ es un grupo abeliano o bien un grupo de Dedekind (todos sus subgrupos son normales). En particular el rank $\CA(\mathbb{Z}_n;A)$ ha sido determinado cuando $n\in\{p,2^k,2^kp:k\geq 1, p\text{ primo impar}\}$.

Ahora bien, oberve que por 4.1 el problema se reduce a calcular $$\Rank\left(\CA(G;A):\ICA(G;A) \right)+\Rank\left(\ICA(G;A)\right),$$ y esto muestra la importancia de calcular $\Rank\left(\ICA(G;A)\right)$.

Así que, en esta última sección compartimos cómo construir cotas superiores elementales para $\Rank\left(\ICA(G;A)\right)$ para el caso particular $G=S_3$ y algunos resultados para $G=S_n$, $G=D_{2n}$ o $G$ un grupo finito en términos de su longitud.

Consideremos el caso del grupo $S_3$, cuya retícula de subgrupos se muestra a continuación.

Observe que el grupo $S_3$ posee seis clases de conjugación de subgrupos: $[H_1]=\{H_1\}$, $[H_2]=\{H_2,H_3,H_4\}$, $[H_5]=\{H_5\}$, $[H_6]=\{H_6\}$. Además, la función de Möbius para la retícula de subgrupos de $S_3$ obedece a las siguientes relaciones:

Dado que $H_1$ es subgrupo maximal de $H_i$ para $i=2,\dots,5$, se tiene que

$$\mu(H_1,H_i)=\cases{ \phantom{-}1 & \text{si $i=1,$} \\ -1 & \text{si $ i=2,\dots,5,$} \\ \phantom{-}3 & \text{si $i=6.$} }$$

Análogamente se puede ver que para $j=2,\dots,5$:

$$\mu(H_j,H_i)= \cases{ \phantom{-}1 & \text{si $i=j$,} \\ -1 & \text{si $i=6$,} \\ \phantom{-}0 & \text{en otro caso}, }$$

mientras que

$$\mu(H_6,H_i)= \cases{ 1 & \text{si $i=6$}, \\ 0 & \text{en otro caso}. }$$

A partir del teorema 3.4 con $n=6$, obtenemos para cada clase, el número de configuraciones en la caja asociada:

\begin{align*} |B_{[H_1]}|&= \mu(H_1,H_1)q^{6}+\mu(H_1,H_2)q^{3}+\mu(H_1,H_3)q^{3}+\mu(H_1,H_4)q^{3}+\mu(H_1,H_5)q^{2}+\mu(H_1,S_3)q \\ &= q^6-3q^3-q^2+3q\\ \\ |B_{[H_2]}|& = \mu(H_2,H_1)q^{6}+\mu(H_2,H_2)q^{3}+\mu(H_2,H_3)q^{3}+\mu(H_2,H_4)q^{3}+\mu(H_2,H_5)q^{2}+\mu(H_2,H_6)q \\ &= 3(q^3-q)\\ \\ |B_{[H_5]}|&= \mu(H_5,H_1)q^{6}+\mu(H_5,H_2)q^{3}+\mu(H_5,H_3)q^{3}+\mu(H_5,H_4)q^{3}+\mu(H_5,H_5)q^{2}+\mu(H_5,H_6)q \\ &= q^2-q\\ \\ |B_{[H_6]}|&= \mu(H_6,H_1)q^{6}+\mu(H_6,H_2)q^{3}+\mu(H_6,H_3)q^{3}+\mu(H_6,H_4)q^{3}+\mu(H_6,H_5)q^{2}+\mu(H_6,H_6)q \\ &= q.\\ \end{align*}

Además, nuevamente por el teorema 3.4 el número de órbitas en cada caja es:

\begin{align*} \alpha_{[H_1]}&=\frac{1}{6}(q^6-3q^3-q^2+3q)\\ \\ \alpha_{[H_2]}&=\frac{2}{6}\cdot 3(q^3-q)=(q^3-q)\\ \\ \alpha_{[H_5]}&=\frac{3}{6} (q^2-q)=\frac{1}{2} (q^2-q)\\ \\ \alpha_{[H_6]}&=\frac{6}{6}q=q. \end{align*}

A continuación calculamos los cocientes $N_G(H_i)/H_i$ para un representante en cada clase $[H_i]$:

\begin{align*} N_{S_3}(H_1)/H_1&=S_3/H_1=S_3\\ \\ N_{S_3}(H_2)/H_2&=H_2/H_2\cong \langle e \rangle\\ \\ N_{S_3}(H_3)/H_3&=S_3/H_3\cong \mathbb{Z}_2\\ \\ N_{S_3}(H_4)/H_4&=S_3/S_3\cong \langle e \rangle.\\ \\ \end{align*}

Ahora podemos aplicar el teorema de estructura 3.3 para caracterizar al grupo $\ICA\left(S_3;A\right)$ en términos de $q=|A|$:

\begin{align*} \ICA\left(S_3;A\right)&\cong \left( S_3 \wr S_{\left[\frac{1}{6}(q^6-3q^3-q^2+3q)\right]}\right)\times \left(\langle e\rangle \wr S_{(q^3-q)}\right)\times \left(\mathbb{Z}_2 \wr S_{\left[\frac{1}{2} (q^2-q)\right]}\right)\times \left(\langle e \rangle \wr S_{q}\right) \\ &\cong \left(S_3 \wr S_{\left[\frac{1}{6}(q^6-3q^3-q^2+3q)\right]}\right)\times S_{(q^3-q)}\times \left(\mathbb{Z}_2 \wr S_{\left[\frac{1}{2} (q^2-q)\right]}\right)\times S_{q}. \end{align*}

El caso particular de un autómata celular con dos estados tiene relevancia en teoría de la computación. Veamos pues que si $q=|A|=2$, se tiene que $\alpha_{H_1}=7$, $\alpha_{H_2}=6$, $\alpha_{H_5}=1$ y $\alpha_{H_6}=2$, dando lugar a la estructura:

\begin{align*} \ICA(S_3;A)&\cong (S_3 \wr S_7)\times (\langle e\rangle \wr S_6)\times (\mathbb{Z}_2 \wr S_1)\times (\langle e \rangle \wr S_2)\\ &\cong (S_3 \wr S_7)\times S_6 \times (\mathbb{Z}_2)^2. \end{align*}

Por lo que a partir del Lema 4.2 tenemos la siguiente cota superior para $\Rank(\ICA(S_3;A))$:

\begin{equation} \label{cotaS} \Rank(\ICA(S_3;A))\leq 2+2+2+2=8. \end{equation}

Con el fin de ilustrar el alcance de nuestra cota, observe que como máximo son necesarios 8 autómatas celulares para generar $$\left|\ICA(S_3;A) \right|=(3!)^7\cdot 7!\cdot 6!\cdot 2\cdot 2!=4,063,327,027,200.$$

Finalmente veamos cómo construir cotas en términos más generales.

Comentarios finales

Espero que esta invitación haya despertado la curiosidad del lector. Para una introducción general al mundo de los autómatas celulares definidos sobre grupos recomiendo consultar [CC10]. Por otro lado, las cotas presentadas aquí se pueden mejorar, el lector interesado puede consultar [CS19]. Agradezco la invitación del Dr. Ángel Zaldivar.

Referencias

AJS09

J Aráujo, J.J. Jarvis y H.D. Sherali The rank of the endomorphism monoid of a uniform partition. Semigroup Forum 78 (2009), 498-510.

Ara+09

J. Araújo, W. Bentz, J. Mitchell y C. Schneider The rank of the semigroup of transformations stabilising a partition of a finite set Mathematical Proceedings of the Cambridge Philosophical Society 159 02 (2009), 339-353.

CC10

T. Ceccherini-Silberstein y M. Coornaert Cellular Automata and Groups Springer 2010.

CG16

A. Castillo-Ramírez y M. Gadouleau Ranks of finite semigroups of one-dimensional cellular automata Semigroup Forum 93 2 (2016), 347-362.

CG17

A. Castillo-Ramírez y M. Gadouleau Cellular Automata and Finite Groups Natural Computing (2017).

CS19

A. Castillo-Ramírez y M. Sánchez-Álvarez Bounding the minimal number of generators of groups and monoids of cellular automata Cellular Automata and Discrete Complex Systems, AUTOMATA 2019 LNCS 11525 (2019), 1-12.

CST89

P. Cameron, R. Solomon y A. Turull Chains of subgroups in symmetric groups Journal of Algebra 127 (1989), 340-352.

Gar70

M. Gardner The game of life. Mathematical games Sci. Am. 223 (1970), 120-123.

GH87

G. M. S. Gomes y J. M. Howie On the rank of certain finite semigroups of transformations Math. Proc. Cambridge Phil. Soc. 101 (1987), 395-303.

HM90

J. Howie y R. McFadden Idempotent rank in finite full transformation semigroups Proceedings of the Royal Society of Edinburgh: Section A Mathematics 114 (3-4) (1990), 161-167.

MP87

Annabelle McIver y Neumann P. Enumerating finite groups Quart. J. Math. 38 2 (1987), 473-488.

Neu66

J. von Neumann Theory of Self-reproducing Automata University of Illinois Press 1966.