Aproximando los escalares de un lambda-cálculo algebraico mediante cotas inferiores
Archivos
Fecha
2011-12-14
Autores
Título de la revista
ISSN de la revista
Título del volumen
Editor
Facultad de Ciencias Exactas, Ingeniería y Agrimensura. Universidad Nacional de Rosario
Resumen
El lambda-cálculo algebraico es un cálculo no tipado en el que se pueden realizar combinaciones lineales de términos, con aplicaciones a la computación probabilística, la computación paralela y la computación cuántica. La reducción en este cálculo está dada por un sistema de reescritura sujeto a varias restricciones que garantizan su confluencia. Existen varios sistemas de tipos para este cálculo, cada uno de los cuales representa un paso más en la dirección a un cálculo algebraico tipado general. En este trabajo, se presenta un sistema de tipos para el lambda-cálculo algebraico que se basa en la idea de aproximar los escalares que aparecen en los términos mediante cotas inferiores, reflejando esta información en los tipos. Se demuestra que este cálculo tiene subject reduction y normalización fuerte, y como corolario se obtiene una forma más sencilla de demostrar la confluencia del sistema de reescritura, eliminando las restricciones a la reducción de la versión no tipada.
Descripción
Palabras clave
cálculos algebraicos, escalares, sistemas de tipos, normalización, confluencia