Indices de Welch

Si bien el concepto de multiplicidad uniforme nos ofrece una caracterización cuantitativa del comportamiento de los ancestros de una secuencia de estados, este concepto no nos dice cual es la mecánica interna del comportamiento de estos antecesores. Para tratar este aspecto haremos uso de los índices de Welch. Este concepto se debe a Lloyd R. Welch el cual trabaja con Hedlund en la elaboración del artículo [Hedlund 69]; Welch expone los índices que llevan su nombre como las distintas partes de los ancestros de una secuencia y cuantos tipos distintos hay de cada parte.

Indice $R$:

• Sea $S \in K^m$ para $m \in \mathbb{Z}^+$.
• Sea $\mathcal{R}_i \subseteq K^n$ para $n \in \mathbb{Z}^+$.
• Sea $E \in K^{m+n-2r}$
• Para que $\mathrm{R} \in \mathcal{R}_i$ debe cumplirse que $\phi(S\mathrm{R})=E$.
• Se tendrá que $R=\max\{r_i\}$, donde $r_i=\vert \mathcal{R}_i \vert$ para toda $i$.

Es decir, dada una secuencia de estados $S$, se formará un conjunto $\mathcal{D}_i$ con aquellas cadenas que al concatenarse con $S$ a la derecha generan la misma evolución. Por supuesto, para cada distinta evolución que sea posible existen distintos conjuntos $\mathcal{R}_i$. Se tomará aquel $\mathcal{R}_i$ con mayor número de estados y su cardinalidad se asignará al índice $R$.

Indice $L$:

• Sea $S \in K^m$ para $m \in \mathbb{Z}^+$.
• Sea $\mathcal{L}_i \subseteq K^n$ para $n \in \mathbb{Z}^+$.
• Sea $E \in K^{m+n-2r}$
• Para que $\mathrm{L} \in \mathcal{L}_i$ debe cumplirse que $\phi(\mathrm{L}S)=E$.
• Se tendrá que $L=\max\{l_i\}$, donde $l_i=\vert \mathcal{L}_i\vert$ para toda $i$.

En otras palabras, para una secuencia de estados $S$, se formará un conjunto $\mathcal{L}_i$ con aquellas cadenas que al concatenarse con $S$ a la izquierda produzcan la misma evolución. Habrá tantos conjuntos ${\cal L}_i$ como evoluciones posibles. Tomaremos aquel de mayor número de estados y su cardinalidad se asignará al índice L. A cada conjunto ${\cal R}_i$ o ${\cal L}_i$ se le denomirá como compatible de $S$ ya sea por la derecha o por la izquierda según corresponda.

Indice $M$:

• Sea ${\cal A}_i = K^m$ para $m \in \mathbb{Z}^+$.
• Sea ${\cal R}_i = K^n$ para $n \in \mathbb{Z}^+$.
• Sea ${\cal L}_i = K^p$ para $p \in \mathbb{Z}^+$.
• Sea $E \in K^{m+n+p-2r}$
• Para que $A \in {\cal A}_i$ debe cumplirse que $\phi({\cal I}_iA{\cal D}_i)=E$.
• Se tendrá que $M=\min\{m_i\}$, donde $m_i=\vert{\cal A}_i \vert$ para toda $i$.

Lo que indica el índice $M$ es el mínimo número de bloques de estados $A$; tal que su evolución con sus conjuntos compatibles izquierdos y derechos particulares es la misma.

Con estos índices se puede contabilizar todas las posibles secciones que tengan los ancestros de una secuencia: a la izquierda, al centro y a la derecha. Sabemos que en un autómata reversible, para toda secuencia $S \in K^m$, debe existir un único estado con el cual regresar en la evolución. Tomando esto como base, los elementos de ${\phi}^{-1}(S)$ concuerdan con un único estado en la misma posición y, de esta posición, se desprenden a la derecha y a la izquierda variaciones que producen las $k^{2r}$ posibilidades. Así, podemos tomar esta posicion idéntica como el conjunto ${\cal A}_i$; dado que esta situación se presenta para todos los ancestros de cada $S$ llegamos a que $\vert{\cal A}_i\vert = 1$ para toda ${\cal A}_i$.

Otra observación importante es acerca del comportamiento de estos ancestros. Una vez que los elementos de ${\phi}^{-1}(S)$ comparten un único estado común con $S \in K^m$; entonces para $T \in K^n$, con $n>m$, los elementos de ${\phi}^{-1}(T)$ siguen conservando a su vez un único estado en común; pues los ancestros de $T$, son originados por extensiones de los ancestros de $S$ que ya comparten un elemento único. Con esto en mente se presenta otro resultado de Hedlund.

Hedlund 4   (Resultado (14.9)) Si el autómata es reversible, entonces $LM=k^{2r}$

Prueba: Sea ${\cal S} = K^m$ con $m \in \mathbb{Z}^+$; numeremos los elementos de ${\cal S}$ con un subíndice. Sabemos que en un autómata reversible toda $S_i \in {\cal S}$ tiene $k^{2r}$ ancestros, los cuales se pueden representar así: ${\phi}^{-1}(S_i)=\{{\cal L}_i {\cal A}_i {\cal R}_i\}$ en donde para toda $S_i$ se cumple que $\vert{\cal A}_i\vert = 1$, un único elemento con el cual regresar en la evolución, esto indica que $M=1$.

Figura 3.7: Ancestros de $S_i$, en donde $M=1$

Para alguna $S_i$ tenemos que $\vert{\cal L}_i\vert = L$ y para alguna otra $S_j$ se cumple que $\vert{\cal R}_j\vert = R$, concatenemos las secuencias $S_iS_j \in K^n$ con $n \in \mathbb{Z}^+$ y $n>m$. $S_iS_j$ sigue conservando un único elemento central $A^{'}$ y cumple, por el resultado (Hedlund 3) que $\vert{\phi}^{-i}(S_iS_j)\vert = k^{2r}$. La forma de estos ancestros es $({\cal L}_i A^{'} {\cal R}_j)$ y se debe cumplir que $\vert({\cal L}_i A^{'} {\cal R}_j)\vert = k^{2r}$.

Figura 3.8: Ancestros de la secuencia $S_iS_j$ con $\vert{\cal L}_i\vert = L$ y $\vert{\cal R}_j\vert = R$

Dado que $\vert A^{'}\vert=1$, $\vert{\cal L}_i\vert = L$ y $\vert{\cal R}_j\vert = R$, se cumple que $LR=k^{2r}$. $\blacksquare$

Este resultado nos dice que en los autómatas reversibles, los índices de Welch contabilizan las diferencias que tienen los ancestros de cada $S \in K^m$ donde $M=1$; el valor $LR=k^{2r}$ implica que estas diferencias se muestran en los extremos y que estos índices son multiplicativos para expresar el número de ancestros de $S$. Un punto a resaltar es que el mínimo valor de $m$ para el cual toda $S \in K^m$ cumple con $M=1$ es la mínima longitud que debe tener cada vecindad en ${\phi}^{-1}$ y el conjunto $S \in K^m$ especifica todas las posibles vecindades de ${\phi}^{-1}$