next up previous contents
Next: Diagramas de Welch y Up: Propiedades de Reversibilidad Basadas Previous: Diagrama de Parejas y   Contenido

Diagrama de Subconjuntos y Propiedades de Reversibilidad

En el principio de este capítulo se hizo la observación que en un autómata reversible no puede existir una configuración que pertenezca al jardín del edén pues esto violaría la biyectividad que debe existir entre el conjunto de configuraciones globales, observar si dichas configuraciones existen o no se puede realizar inspeccionando el diagrama de subconjuntos, en un autómata reversible observaremos que no existirá una ruta que vaya desde el conjunto completo hasta el conjunto vacío en este diagrama.

Otra información importante es que por medio de esta gráfica podemos conocer cual es el valor de los índices de Welch, si observamos cual es el nivel máximo que podemos alcanzar empezando desde los conjuntos unitarios estaremos conociendo el valor del índice $R$, a continuación reflejemos la regla de evolución, esto es, tomemos en sentido inverso las vecindades conservando su mapeo original y de esta regla reflejada formemos su diagrama de subconjuntos, haciendo el mismo análisis, veamos hasta que nivel llegamos empezando desde las clases unitarias y este nivel indicará el valor de $L$.

El proceso anterior funciona ya que las clases unitarias son nodos aislados de de Bruijn, de estos nodos deben surgir todas las posibles variaciones a la derecha para una secuencia dada, y en todos los casos el número de variaciones debe ser $R$, de aquí que estas rutas lleguen hasta el nivel $R$ al cual lo conforman subconjuntos con este número de elementos señalando las posibilidades existentes que tienen de terminar los ancestros de cada ruta, lo análogo sucede en la regla reflejada y el nivel $L$.

Se vio también que una vez se han fijado en los ancestros de una cadena los valores de $L$ y $R$, estos se conservan no importando que tanto y hacia que dirección extendamos dicha cadena; por esta razón veremos que en el diagrama de subconjuntos empezando desde las clases unitarias, las rutas llegan al nivel $R$ y ya no saldrán de este nivel conservando el valor del índice $R$, lo mismo ocurre con el diagrama de subconjuntos de la regla reflejada, de los conjuntos unitarios las rutas llegarán al nivel $L$ y sus continuaciones se seguirán manteniendo en dicho nivel.

Gracias a la propiedad anterior, del diagrama de subconjuntos de la regla original podemos obtener el diagrama de Welch derecho, y del diagrama de subconjuntos de la regla reflejada se puede generar el diagrama de Welch izquierdo, pues como explicamos con anterioridad, los nodos de estos diagramas no son más que subconjuntos de $R$ elementos y $L$ elementos respectivamente y estos por definición deben aparecer en el diagrama de subconjuntos, así, si observamos en el diagrama de subconjuntos de la regla original que familia de nodos del nivel $R$ tienen todas sus rutas autocontenidas en la misma, esta familia contiene los nodos del diagrama de Welch derecho, el proceso similiar ocurre para el diagrama de Welch izquierdo, en la gráfica de subconjuntos de la regla inversa observemos en el nivel $L$ que familia de nodos conducen todas sus posibles rutas hacia si misma y en esta familia tendremos los nodos del diagrama de Welch izquierdo.


next up previous contents
Next: Diagramas de Welch y Up: Propiedades de Reversibilidad Basadas Previous: Diagrama de Parejas y   Contenido
ice 2001-08-31