Más Propiedades de los Indices de Welch

Nasu hace importantes observaciones sobre el comportamiento de los ancestros en un autómata reversible por medio de los índices de Welch. De la misma forma que se mostraron los resultados de Hedlund; el enfoque de Nasu es tratado en esta sección haciendo referencia de los resultados a usar con $(Resultado (m.n))$ que corresponden a la sección $(m.n)$ de la referencia [Nasu 78]. l

Nasu 1   (Resultado (5.1)) Sea $m$ el tamaño mínimo de las vecindades de ${\phi}^{-1}$, sea ${\cal S}=K^n, n \geq m$. Si ${\cal L}_i{\cal A}_i{\cal R}_i$ son los ancestros de cada $S \in {\cal S}$, entonces se cumple que:

• $\mid {\cal L}_i \mid = L$
• $\mid {\cal R}_i \mid = R$

para toda $S \in {\cal S}$

Prueba:Iniciemos con la proposición que para cada $S \in {\cal S}$, se tiene que $\vert{\cal L}_i\vert \leq L$ y $\vert{\cal R}_i\vert \leq R$.

Figura 3.9: Ancestros de $S$ con $\vert{\cal L}_i\vert \leq L$ y $\vert{\cal R}_i\vert \leq R$

Por el lado izquierdo, supongamos que para alguna $S \in \mathcal{S}$ se tiene que $\vert{\cal L}_i\vert < L$, Dado que para $S$ ya se fijó un único elemento ${\cal A}_i$, los ancestros deben mostrar sus diferencias en ${\cal L}_i$ y en ${\cal R}_i$. Debido a que $\vert{\cal L}_i\vert < L$; se tiene $\vert{\cal I}_i\vert\vert{\cal D}_i\vert < LR = k^{2r}$ lo cual contradice la multiplicidad uniforme (Resultado 2 en la sección 3.4).

De manera análoga la demostración se lleva para el lado derecho con $\mathcal{R}_i$. De los resultados anteriores concluimos que $\vert{\cal L}_i\vert = L$ y $\vert{\cal R}_i\vert=R$.

Figura 3.10: Si $\mid {\cal I}_i \mid < L$ entonces $\mid {\cal I}_i \mid \mid {\cal D}_i \mid < LR = k^{2r}$ contradiciendo a la multiplicidad uniforme

Si extendamos a $S$ hacia la izquierda concatenandole estados, entonces ${\phi}^{-1}(S)=\{{{\cal L}^{'}}_{i} {\cal A}_{i} {\cal R}_{i}\}$. Dado que $\vert{\cal R}_{i}\vert = R$ y $\vert{\cal A}_i\vert = 1$ se mantienen , entonces $\vert{{\cal L}^{'}}_{i}\vert$ debe seguir siendo igual a $L$ pues de otro modo no se cumple con la multiplicidad uniforme; esto es análogo si extendemos $S$ a la derecha.

Figura 3.11: Extensiones de $S$ siguen conservando el valor de los índices $L$ y $R$

Por lo tanto, $\vert{\cal L}_i\vert = L$ y $\vert{\cal R}_i\vert=R$ para toda $S \in K^n$ con $n \geq m$. $\blacksquare$

La nota concluyente de este resultado es que en un autómata reversible, los ancestros de todas las posibles secuencias de longitud mayor o igual a las de las vecindades de la regla inversa ya tienen bien definidos sus índices $L$ y $R$ y estos valores se conservan no importando que tanto extendamos dichas secuencias ni en que dirección.

Del resultado anterior se desprende otro importante acerca de la relación entre los conjuntos compatibles izquierdos y derechos.

Nasu 2   (Resultado (3)) Sea $m$ el tamaño mínimo de las vecindades de ${\phi}^{-1}$, sea ${\cal S}=K^n$ con $n \geq m$. Si ${\cal L}_i{\cal A}_i{\cal R}_i$ son los ancestros de cada $S_i \in {\cal S}$, entonces para $S_i$ y $S_j \in {\cal S}$ se cumple que $\vert{\cal R}_i \cap {\cal L}_j\vert = 1$.

Prueba: Tomemos a ${\phi}^{-1}(S_i)=({\cal L}_i {\cal A}_i {\cal R}_i)$ y a ${\phi}^{-1}(S_j)=({\cal L}_j {\cal A}_j {\cal R}_j)$. Si formamos la cadena $S_iS_j$, entonces ${\phi}^{-1}(S_iS_j)=({\cal L}_{i} {\cal A}_{i} ({\cal R}_{i} \cap {\cal L}_{j}) {\cal A}_{j} {\cal R}_{j})$. Si $({\cal R}_{i} \cap {\cal L}_{j})=\emptyset$ entonces no se podrá formar un ancestro de $S_iS_j$ y ésta será una cadena del jardín del edén, situación que no puede ser en un autómata reversible.

Figura 3.12: Si ${\cal D}_i \cap {\cal I}_j = \emptyset$ entonces la cadena pertenece al jardín del edén y el autómata no es reversible

Por otro lado, si $\vert{\cal R}_{i} \cap {\cal L}_{j}\vert>1$ para ${\cal A}_i$ se tendrá un conjunto compatible derecho de la forma $({\cal R}_{i} \cap {\cal L}_{j}) {\cal A}_{j} {\cal R}_{j})$ en donde $\vert({\cal R}_{i} \cap {\cal L}_{j}) {\cal A}_{j} {\cal R}_{j})\vert > R$ ya que para cada elemento de $({\cal R}_{i} \cap {\cal L}_{j})$ existirán tantas posibilidades de continuar a la derecha como $\vert{\cal R}_j\vert = R$ generando en total un valor mayor que $R$, lo cual contradice el resultado (Nasu 1).

Figura 3.13: Si ${\cal D}_i \cap {\cal I}_j >1$ entonces la cadena tiene más ancestros que $k^{2r}$ contradiciendo la multiplicidad uniforme

Por lo tanto $\vert{\cal R}_{i} \cap {\cal L}_{j}\vert=1$. $\blacksquare$

Lo que nos expone el resultado (Nasu 2) es que las extensiones compatibles derechas e izquierdas de toda vecindad inversa de ${\phi}^{-1}$ intersectan en un solo elemento y esto se mantiene para todas las posibles extensiones de cada vecindades de ${\phi}^{-1}$. Algo más sútil que puede encontrarse en el resultado anterior es que, cuando solamente concatenamos los ancestros de las secuencias $S_i$ y $S_j$, la evolución de estos antecesores tiene la forma $S_iES_j$ donde $E \in K^{2r}$.

Si ahora solamente queremos a $S_iS_j$ en la evolución debemos traslapar los ancestros de ambas cadenas y estos solo deben traslapar de una forma posible como se demostró en (Nasu 2). Lo importante es ver que el tamaño del traslape es $2r$, es decir, los ancestros concuerdan en sus $2r$ elementos extremos, o lo que es lo mismo, en un nodo de de Bruijn.