Diagramas de Welch

Tomemos los diagramas de Welch del autómata $(4,1/2)$ regla $1B2D1E2D$.

Figura 6.5: Diagramas de Welch del autómata celular lineal reversible $(4,1/2)$ regla $1B2D1E2D$

Como se señaló en el capítulo 3, Nasu aplica la teoría de autómatas definidos desarrollada en [Perles 63] a los diagramas de Welch. Con esto se tiene que el diagrama derecho de Welch es $p-definido$ si empezando desde cualquier subconjunto, una misma secuencia de estados con longitud mayor o igual que $p$ finaliza en un único subconjunto; análogamente, el diagrama izquierdo de Welch es $q-definido$ si empezando desde cualquier subconjunto, una misma secuencia de estados con longitud mayor o igual a $q$ finaliza en un único subconjunto.

Por ejemplo; en la Figura 6.5, para el diagrama de Welch derecho del autómata $(4,1/2)$ vemos que empezando desde cualquier subconjunto, para la secuencia $2$, existen $3$ subconjuntos finales distintos, para la secuencia $22$ existen $2$ subconjunto finales diferentes y para la secuencia $222$, sólo hay un único subconjunto final. Haciendo un estudio completo para todas las demás secuencias, llegamos a que este diagrama es $3-definido$.

Un resultado importante relacionado con nuestro problema lo da Nasu en [Nasu 78] en el Teorema $7$, en donde define que el tamaño de la mínima vecindad de la regla inversa está dado por $p+q-(2r+1)+2$, donde $r$ es el radio de vecindad de la regla original y $p$, $q$ son las longitudes para las cuales son definidos los diagramas de Welch derecho e izquierdo respectivamente del autómata. Entonces, para contestar que tan grande puede ser la mínima vecindad inversa sólo necesitamos saber que tan grande puede ser $p$ y $q$ en un autómata reversible.

Sea $W_r$ el número de nodos del diagrama derecho de Welch, en el trabajo de Nasu [Nasu 78] Teorema $g$, encontramos que si este diagrama de $p-definido$, entonces $p \leq W_r-1$, esto es análogo para el diagrama de Welch izquierdo. Así, nuestro problema se puede resolver si contestamos cual es el máximo número de nodos que pueden tener ambos diagramas, lo cual tampoco es algo sencillo de responder.

Sin embargo, si en el autómata reversible alguno de sus índices $L$ o $R$ es igual a $1$, entonces conocemos como va a ser la estructura de ambos diagramas. Si $R=1$, el diagrama de Welch derecho es isomorfo al diagrama de de Bruijn, y tendrá tantos nodos como éste, en tanto que el diagrama de Welch izquierdo estará formado por un único nodo, en otras palabras a lo más $p=d-1$ y $q=0$. Si aplicamos el resultado de Nasu al autómata $(4,1/2)$ que hemos estado manejando, tenemos que el máximo tamaño de la mínima vecindad inversa está dado de la siguiente forma.

$$p+q-(2r+1)-2= d-1 + 0 - (2(1/2)+1) -2 = d-1$$ (6.1)

El máximo tamaño es igual al número de nodos del diagrama de de Bruijn menos uno.