Obteniendo la Regla Inversa $\phi ^{-1}$ de las Permutaciones $p_1$

Hasta ahora hemos visto que propiedades deben cumplir las permutaciones $p_1$ en un autómata reversible, veamos entonces como se puede obtener la regla inversa $\phi ^{-1}$ de una permutación $p_1$ dada. Usemos como referencia los bloques correspondientes tanto a $L_\phi$ como a $R_\phi$ descritos en la Figura 5.5.

Figura 5.5: Bloques que forman los conjuntos $L_\phi$ y $R_\phi$

Para la regla inversa $\phi ^{-1}$ el papel de estas posiciones se intercambia. Es decir, en los bloques de $L_\phi$, lo que era la parte izquierda del ancestro ahora es la evolución derecha y, lo que era la parte de la evolución izquierda, pasa a ser la parte derecha del ancestro. En los bloques de $R_\phi$, lo que era la parte derecha del ancestro ahora actua como evolución izquierda y lo que era evolución derecha actuará como parte izquierda del ancestro.

Tabla: Papel que juegan las celulas de los bloques $(a_le_l)$ y $(a_re_r)$ para la regla original y la regla inversa

$L_\phi$	$\rightarrow$	$R_\phi^{-1}$
$a_l$	$\rightarrow$	$e'_r$
$e_l$	$\rightarrow$	$a'_r$

$R_\phi$	$\rightarrow$	$L_\phi^{-1}$
$a_r$	$\rightarrow$	$e'_l$
$e_r$	$\rightarrow$	$a'_l$

Entonces, podemos hacer particiones en el conjunto $L_\phi$, en donde los elementos de cada partición coincidan en la posición $a_l$; y del mismo modo podemos particionar el conjunto $R_\phi$ en donde los elementos de cada partición coincidan en la posición $a_r$. En ambos casos tendremos $k$ particiones pues en estas posiciones se encuentran todos los elementos de $K$. Sea $i \in K$ un estado del autómata, para cada partición $i$ en $L_\phi$ se tendrán $L$ elementos distintos en la posición $e_l$; que son al mismo tiempo elementos de la posición $a'_r$ en $R_\phi^{-1}$, sabiendo que el indice de Welch derecho de $\phi ^{-1}$ es igual a $L$. De esta manera para cada partición $i$ formemos el conjunto $E_{l_i}$ con los elementos en $e_l$. De manera análoga, para cada partición $i$ en $R_\phi$ se tendrán $R$ elementos distintos en $e_r$ que a su vez es $a'_l$, tomemos estos y formemos el conjunto $E_{r_i}$ con los elementos en $e_r$.

Con estas particiones podemos entonces formar a $\phi ^{-1}$, para $i \in K$, en la regla inversa cada estado $i$ tendrá $R$ estados izquierdos ancestros especificados en $E_{r_i}$ y $L$ estados derechos ancestros especificados en $E_{l_i}$, entonces, la concatenación de todos los elementos del conjunto $E_{r_i}$ con todos los elementos del conjunto $E_{l_i}$ nos darán todas las vecindades ancestras del estado $i$.