First LIA doctoral thesis in cotutelle — Defense set for 7/Nov/2014

Carlos Lombardi will be defending his PhD thesis Friday 7 November at 11AM in room E24 at the Departamento de Computación, FCEyN, UBA.

Directores argentinos: Dr. Alejandro Ríos, Dr. Eduardo Bonelli

Director francés: Dra. Delia Kesner

Jurados:
Dr. Mauricio Ayala Rincón (Universidad de Brasilia)
Dr. Alexandre Miquel (Universidad de París)
Dr. Nazareno Aguirre (Universidad Nacional de Río Cuarto)

Título: Espacios de reducción en sistemas de reescritura no-secuenciales e infinitarios

Resumen:
En esta tesis estudiamos distintos aspectos ligados al espacio de
reducción de diversos sistemas de reescritura.
Los sistemas abarcados presentan características que hacen que el
estudio de sus espacios de reducción diste de ser una tarea sencilla.

Las principales contribuciones son:
(1) se define una estrategia de reducción multipaso para el Pure Pattern
Calculus, un cálculo con patrones no-secuencial, y se demuestra que
dicha estrategia es normalizante;
(2) se propone un criterio para formalizar el concepto de reducción
standard en el Linear Substitution Calculus, un cálculo de sustituciones
explícitas cuyas reducciones se consideran módulo una relación de
equivalencia sobre su conjunto de términos, obteniéndose un resultado de
unicidad de reducciones standard para el criterio definido; y
(3) se caracteriza la equivalencia entre reducciones para los sistemas
de reescritura de términos infinitarios de primer orden y lineales a
izquierda, utilizándose esta caracterización para desarrollar una
demostración alternativa del resultado de compresión.

Destacamos el uso de modelos genéricos de sistemas de reescritura: se
utiliza una formulación de Sistemas Abstractos de Reescritura para
estudiar el Pure Pattern Calculus y el Linear Substitution Calculus, y
un modelo basado en Proof Terms para estudiar la reescritura
infinitaria. Esta tesis incluye asimismo extensiones de los dos modelos
genéricos utilizados, que pueden considerarse contribuciones adicionales
de la misma.

Bookmark the permalink.