Formando el Diagrama de Welch

Hemos establecido que en un autómata reversible, las cadenas de una longitud dada tienen un único elemento con el cual regresan hacia atrás en la evolución, por lo que estas cadenas funcionan como las vecindades de tamaño mínimo de la regla inversa, en dichas secuencias se cumplen las siguientes propiedades:

• Toda secuencia tiene el mismo número de ancestros.
• El número de ancestros es igual a ${k}^{2r}$.
• La forma de los ancestros de cada secuencia se puede representar como $({\cal L}_{i} {\cal A}_{i} {\cal R}_{i})$.
• $\mid {\cal L}_{i} \mid = L$
• $\mid {\cal A}_{i} \mid = 1$
• $\mid {\cal R}_{i} \mid = R$
• $LR={k}^{2r}$.
• $\vert{\cal R}_{i} \cap {\cal L}_{i}\vert=1$ para todo posible ${\cal R}_{i}$ y ${\cal L}_{i}$.
• El tamaño del traslape de ${\cal R}_{i} \cap {\cal L}_{i}$ es de $2r$.

De lo anterior se desprende que si para cada vecindad inversa solo utilizamos los $2r$ elementos extremos distintos de los ancestros, con estos podemos formar todos los posibles conjuntos $\mathcal{L}_i$ y $\mathcal{R}_i$. Tomemos todas las clases $\mathcal{L}_i$ y con éstas establezcamos un diagrama que será llamado diagrama de Welch izquierdo. Va a existir una arista de un nodo hacia otro si del inicial se tiene un conjunto de elementos con al menos un miembro; de tal modo que, en el diagrama de de Bruijn este conjunto este ligado con el mismo tipo de liga con todos los elementos del conjunto final, tal como se hizo en el diagrama de subconjuntos. Haciendo el proceso análogo para todas las clases $\mathcal{R}_i$ obtenemos el diagrama de Welch derecho.

Una vez construidos ambos diagramas para un autómata reversible particular, Nasu aplica en ellos la teoría de autómatas definidos dada en [Perles 63]. El diagrama de Welch derecho es $p-definido$ si empezando desde cualquier nodo, una misma secuencia de longitud mayor o igual a $p$ finaliza en un único nodo; del mismo modo, el diagrama de Welch izquierdo es $q-definido$ si empezando desde cualquier nodo, una misma secuencia de longitud mayor o igual a $q$ finaliza en un único nodo.

Una pregunta inmediata es: ¿que tan grandes pueden ser los valores de $p$ y $q$?. Sea $WI$ el número de nodos del diagrama de Welch izquierdo y sea $WD$ el número de nodos del diagrama de Welch derecho, entonces del Teorema 1 de [Perles 63] tenemos que:

$$\begin{array}{c} p \leq WD-1 \\ q \leq WI-1 \end{array}$$ (3.3)

Un uso inmediato de los diagramas de Welch es conocer cual es elemento único con el que una cadena debe regresar hacia atrás en la evolución, esto se puede hacer tomando el diagrama de Welch izquierdo y encontrar a que nodo llega toda posible instancia de una ruta $r_i$ dada, hacemos lo mismo con el diagrama de Welch derecho para toda instancia de una ruta $r_j$. Dado que los nodos del diagrama izquierdo son conjuntos ${\cal L}_i$, los nodos del diagrama derecho son conjuntos ${\cal R}_j$ y ${\cal L}_i \cap {\cal R}_j = e$ con $e \in K^{2r}$; el nodo final de la ruta $r_i$ y el nodo inicial de la ruta $r_j$ concuerdan en una única secuencia $e$ de tamaño $2r$, así, la cadena formada concatenando $r_ir_j$ tiene una sola forma de regresar hacia atrás en la evolución seleccionando un estado de $e$.