Next: Diagrama de Subconjuntos Up:
Introducción al Estudio de Previous: Diagrama de de
El diagrama de Subconjuntos es un derivado del diagrama de de Bruijn, se usa
principalmente para obtener todas las configuraciones que puedan evolucionar en una
configuración deseada, es decir, encontrar ancestros. Una excelente aplicación de la
construcción del diagrama de Subconjuntos es la búsqueda del Jardín del Edén,
es decir, configuraciones que no tienen ancestros.
McIntosh [2] da dos razones importantes para trabajar
con diagramas de Subconjuntos.
- Etiquetar ligas da la apariencia de funciones, ya que asocia unos objetos con otros,
pero si dos ligas con la misma etiqueta surgen de un mismo vértice, ellas dificilmente
pueden representar una función; construyendo el diagrama de Subconjuntos de todos
los destinos, deja una simple liga entre éstos, brindando funcionalidad al diagrama
aunque ésta no existiera originalmente, la inclusión del conjunto vacio asegura que cada
punto tiene una imagen, permitiendo parcialmente definir funciones.
- Una vez que el diagrama de Subconjuntos ha sido formado, se ve si un camino va
del conjunto universal al conjunto vacio, esto es evidencia decisiva de que tal ruta no
existe en el diagrama original.
Otra aplicación es determinar donde existen rutas partiendo de las clases unitarias,
tales rutas pueden ser usadas para forzar un autómata dentro de un estado predeterminado,
no importando su condición original.
Genaro Juárez Martínez
E-mail:genaro@sparcomp.cs.cinvestav.mx
Seck Tuoh Mora Juan Carlos
E-mail:seck@delta.cs.cinvestav.mx