Tesis doctoral de Francesc Xavier Babot Pagés
Los métodos de verificación formal se están usando cada vez más en la industria para establecer la corrección y encontrar los errores en modelos de sistemas; por ejemplo, la descripción de hardware, protocolos, programas distribuidos, etc. En particular, los verificadores de modelos lo hacen automáticamente para sistemas de estados finitos, pero están limitados debido al problema de la explosión de estados; y la verificación formal interactiva, el área de esta tesis, es necesaria. el enfoque de la verificación automática trabaja sobre el sistema de transiciones del modelo, el cual define su semántica. Este sistema de transiciones tiene a menudo muchos estados, y siempre un tamaño grande comparado con el tamaño del modelo del sistema, el cual es siempre infinito. Estas consideraciones sugieren un enfoque de verificación estática como los de esta tesis, evitando los sistemas de transiciones, trabajando directamente sobre el modelo del sistema, en principio, la complejidad computacional tendría que ser menor. El enfoque estático de este trabajo se lleva a cabo sobre modelos de sistemas expresados en notación imperativa con paralelismo explícito, sentencias de comunicaciones síncronas y variables de almacenamiento locales. los razonamientos de equiValencia son muy empleados para números, matrices y otros campos. Sin embargo, para programas imperativos con paralelismo, comunicaciones y variables, aún teniendo la potencialidad de ser un método de verificación muy intuitivo, no han sido muy explorados. La secuencialización formal vía la eliminación de comunicaciones internas, el área de esta tesis, es una demostración basada en el razonamiento estático de equiValencias que, ya que disminuye la magnitud del vector de estados, puede complementar otros métodos de demostración. Se basa en la aplicación de un conjunto de leyes, apropiadas para tal propósito, como reducciones de reescritura del modelo del sistema. éstas dependen de la noción de equiValencia y de las suposiciones de justicia. esta tesis contribuye a la casi inexplorada área de la eliminación de comunicaciones formal y secuencialización de modelos de sistema. Las leyes están definidas sobre una equiValencia débil: equiValencia de interfaz. La eliminación de comunicaciones está limitada a modelos sin selecciones, por ejemplo modelos en los cuales las comunicaciones internas no están dentro del ámbito de sentencias de selección. Aplicaciones interesantes existen dentro de este marco. Las leyes son válidas sólo para justicia débil o sin justicia. ésta ha sido desarrollada siguiendo la semántica propuesta por manna y pnueli para sistemas reactivos [mp91, mp95]. Se han formulado las condiciones de aplicabilidad para las leyes de la propia eliminación de comunicaciones. Además, se propone un procedimiento de construcción de demostraciones para la eliminación de comunicaciones, el cual intenta aplicar automáticamente las leyes de la eliminación. También se ha diseñado un conjunto de procedimientos de transformación, los cuales garantizan que la transformación equivalente siempre corresponde a la aplicación de una secuencia de leyes. Debido a que la construcción de las demostraciones es impracticable, normalmente imposible, sin la ayuda de una herramienta, se ha desarrollado un demostrador interactivo para la construcción semiautomática de la secuencialización de modelos de sistemas y demostraciones de eliminación. Tanto los procedimientos de transformación como los de la eliminación de comunicaciones están integrados en la herramienta. Con la ayuda del demostrador se ha construido la demostración de secuencialización de un modelo, no trivial, de procesador pipeline. Para este ejemplo se ha logrado una reducción, respecto del modelo original, de la cota superior del número de estados de 2-672. a pesar de la enorme cantidad de esfuerzo dedicado al área, antes y durante esta tesis, todavía queda mucho trabajo para que la eliminación de comunicaciones y la secuencialización sea realmente un método práctico. Sin embargo los resultados de esta tesis han establecido los cimientos y han dado el estímulo necesario para continuar el esfuerzo.
Datos académicos de la tesis doctoral «Contributions to formal communication elimination for system models with explicit parallelism«
- Título de la tesis: Contributions to formal communication elimination for system models with explicit parallelism
- Autor: Francesc Xavier Babot Pagés
- Universidad: Ramón llull
- Fecha de lectura de la tesis: 09/10/2009
Dirección y tribunal
- Director de la tesis
- Miquel Bertran Salvans
- Tribunal
- Presidente del tribunal: zohar Manna
- Fernando Lopez pelayo (vocal)
- bernd Finkbeiner (vocal)
- ricardo Peña marí (vocal)