Defensa Tesis Licenciatura Gervasio Pérez

Los sistemas de tiempo real son por naturaleza críticos. Sus fallas pueden resultar en serias pérdidas, tanto materiales como también de vidas humanas. Además, en general están descriptos por la interacción de varios componentes y resulta muy difícil asegurar que determinadas propiedades (que representan de alguna manera requisitos o condiciones deseables del sistema) se cumplan. Hoy en día existen herramientas denominadas model checkers (por ejemplo, UPPAAL, HyTech, KRONOS) utilizadas para expresar y verificar propiedades sobre este tipo de sistemas. Una de las propiedades más requerida es la de establecer si cierto conjunto de estados del sistema es o no alcanzable desde un estado inicial determinado. Esta verificación es costosa, y a veces prohibitiva, en términos de tiempo y memoria, debido al problema de la explosión combinatoria de estados. Recientemente se ha estudiado el uso de estructuras de decisión como posible alternativa a las representaciones clásicas utilizadas en la verificación, de forma de lograr reducir, en cierto grado, los efectos de tal explosión. En este trabajo se estudia la presencia de redundancia interna en una estructura de datos presentada basada en árboles de decisión. Primero cuantificamos dicha redundancia y luego implementamos un método para hacer aliasing de las partes repetidas de la estructura, efectivamente reduciendo el espacio consumido.