Herramientas Personales
Usted está aquí: Inicio / Agenda / Defensa Tesis Licenciatura Elisa Orduna

Defensa Tesis Licenciatura Elisa Orduna

Título: Preservación de normalidad en transductores. Directores: Verónica Becher y Olivier Carton. Jurados: Sergio Abriola y Santiago Figueira.

Detalles del evento

Cuándo

19/07/2018
de 17:00 a 18:00

Dónde

Aula 2

Agregar evento al calendario

  • Título: Preservación de normalidad en transductores.
  • Directores: Verónica Becher y Olivier Carton.
  • Jurados: Sergio Abriola y Santiago Figueira.
  • Resumen:

En esta tesis se plantea el problema de determinar si un transductor finito determinı́stico dado devuelve una palabra normal siempre que recibe como entrada una palabra normal, es decir, si preserva normalidad. Una palabra infinita x es normal si todos los bloques de igual tamaño aparecen en x con la misma frecuencia asintótica. Hay algunas familias conocidas de transductores finitos que preservan normalidad, entre ellos los selectores de Agafonov y los transductores que eliminan todas las apariciones de un símbolo dado (en alfabetos con al menos tres sı́mbolos). En la tesis desarrollamos un algoritmo ideado por Olivier Carton que decide si un transductor determinı́stico preserva normalidad. Lo hace en tiempo polinomial. En primer lugar, el algoritmo obtiene una descomposición del transductor en componentes fuertemente conexas y analiza todas aquellas que sean recurrentes. Para cada componente el algoritmo construye un autómata con pesos que permite calcular la frecuencia de una palabra finita arbitraria en la salida, suponiendo que la entrada es una palabra normal. Por último, el algoritmo verifica que estas frecuencias sean las esperadas utilizando el algoritmo polinomial que surge de la caracterización dada por Schützenberger. Además, en la tesis presentamos un prototipo en Python que implementa el algoritmo.