Proceso de Kari

Kari define el siguiente proceso para autómatas con $r=1/2$ ya que con estos podemos simular todo tipo de aut'omatas como se mostró en el capítulo 5 sección 5.2. Tomemos para ejemplificar este procedimiento el autómata reversible $(4,1/2)$ regla $FFA91640$.

Tabla 6.2: Autómata $(4,1/2)$ regla $FFA91640$

$\begin{array}{ccccc} &0&1&2&3 \\ \cline{2-5} \multicolumn{1}{c\vert}{0}& 0&0&... ...c\vert}{2}& 1&2&2&2 \\ \multicolumn{1}{c\vert}{3}& 3&3&3&3 \\ \end{array}$

Este autómata tiene como valores de sus índices de Welch, $L=1$ y $R=4$; debido a esto en la regla de evolución cada columna tiene una sola entrada para cada estado, es decir, cada columna es una permutación del conjunto $K$. Esta cualidad, que siempre se presenta en este tipo de autómatas, Kari la aprovecha de la siguiente manera: sabemos que la regla de evolución $\phi$ mapea vecindades a estados.

$$\phi(ab) \rightarrow s \mbox{ para } ab \in K^2 \mbox{ y } s \in K$$ (6.2)

Por lo tanto, como en la regla de evolución cada columna tiene a todos los estados y estos parecen una sola vez cada uno, podemos definir la siguiente función.

$$\varphi_s(b)=a,\mbox{ si } \phi(ab)=s$$ (6.3)

Por ejemplo, el autómata $(4,1/2)$ regla $FFA91640$ especificado en la Tabla 6.2 cumple que $\phi(20)=1$ por lo que $\varphi_1(0)=2$. Podemos extender esta definición para cadenas arbitrarias de elementos de la siguiente manera.

$$\begin{array}{rcl} \varphi_\lambda (b) &=&b, \mbox{ para tod... ... \mbox{ para toda } w \in K^* \mbox{ y } b,s \in K. \end{array}$$ (6.4)

En donde $\lambda$ simboliza a la palabra vacía, así, retomando el autómata $(4,1/2)$ regla $FFA91640$ que se muestra en la Tabla 6.2, tenemos que:

$$\begin{array}{l} \varphi_0(3)=1 \\ \varphi_{30}(3)=\varphi_... ...130}(3)=\varphi_1(\varphi_{30}(3))=\varphi_1(3)=0 \end{array}$$

Usemos la función $\varphi_w$ y definamos una jerarquía de relaciones $\rho_i \subseteq K \times K, i \geq 0$ de la siguiente forma:

$$(a,b) \in \rho_i \mbox{ si y solo si } \rho_w(a) = \rho_w(b) \mbox{ {\bf para todo} } w \in K^i$$ (6.5)

Kari demuestra en [Kari 92] que las relaciones así definidas cumples con las siguientes propiedades:

1. $\rho_i$ son relaciones de equivalencia.
2. $\rho _0$ es la relación identidad sobre $K$.
3. $\rho_i \subseteq \rho_{i+1}$ para cada $i \geq 0$.
4. $\rho_t$ es la relación completa $K \times K$ para alguna $t \geq 0$.
5. $\rho_i \neq \rho_{i+1}$ si $\rho_i \neq K \times K$.

Al número de clases de equivalencia distintas de $\varphi_i$ lo denotaremos como $c_i$. Para $\rho _0$ tenemos que existen tantas clases de equivalencia como estados haya en el autómata o nodos en el diagrma de de Bruijn pues $r=1/2$, es decir, $c_0=d=k$. De las propiedades $3$ y $5$, llegamos a que $c_{i+1} \leq c_i$ para toda $i \geq 0$, y $c_{i+1} < c_i$ si $c_i > 1$. Así tenemos que en el peor caso $c_{k-1}=1$ y que $\rho_{k-1}=K \times K$, esto significa que en los ancestros de toda cadena de longitud menor o igual a $k-1$ exiten tantas terminaciones derechas como $k$ y una única terminación izquierda, por lo que para esa cadena, ha quedado fijo un único elemento con el cual regresar hacia atrás en la evolución, concluyendo así que el máximo tamaño de la mínima vecindad inversa es $k-1$.

Utlizando el autómata $(4,1/2)$ de la Tabla 6.2, primero tomemos las $4$ clases distintas que por definición existen para $\rho _0$, o sea, tomando la palabra vacía $\lambda$.

Tabla 6.3: Clases de equivalencia $\rho _0$

$\begin{array}{cccc} \mbox{Clase 0}&\mbox{Clase 1}&\mbox{Clase 2}&\mbox{Clase 3... ...ert}{2}& \\ \multicolumn{1}{c\vert}{3}& &&&1 \\ \end{array} \\ \end{array}$

Formemos ahora las relaciones $\rho _1$, observemos que para construir $\rho _1$, basta con revisar cada columna de la regla de evolución en la Tabla 6.2. Las columnas $1$ y $2$ son idénticas, por lo que estos elementos forman una única clase, las columnas $0$ y $3$ siguen formando clases individuales.

Tabla 6.4: Clases de equivalencia $\rho _1$

$\begin{array}{ccc} \mbox{Clase 0}&\mbox{Clase 1,2}&\mbox{Clase 3} \\ \begin{a... ...ert}{2}& \\ \multicolumn{1}{c\vert}{3}& &&&1 \\ \end{array} \\ \end{array}$

Para obtener $\rho _2$, se toman todas las cadenas de $2$ elementos y sus ancestros:

Tabla 6.5: Cadenas de longitud $2$ y sus ancestros

$\begin{array}{\vert cccccccc\vert} \hline \multicolumn{8}{\vert c\vert}{} \\ ... ... \hline \end{array} \\ \multicolumn{8}{\vert c\vert}{} \\ \hline \end{array}$

Se observa en la Tabla 6.5 que en los ancestros de estas secuencias, los estados $0,1,2$ forman una sola clase ya que para toda cadena $w \in K^2$, se tiene que $\varphi_w(0)=\varphi_w(1)=\varphi_w(2)$. Esto no ocurre con el estado $3$, que sigue conservándose como una clase individual.

Tabla 6.6: Clases de equivalencia $\rho _2$

$\begin{array}{ccc} \mbox{Clase 0,1,2}&&\mbox{Clase 3} \\ \\ \begin{array}{ccc... ...ert}{2}& \\ \multicolumn{1}{c\vert}{3}& &&&1 \\ \end{array} \\ \end{array}$