Artículo:
Indecidibilidad del análisis de dependencias de datos

Fecha

2023-09-12

Editor

Sistedes

Publicado en

Actas de las XXII Jornadas sobre Programación y Lenguajes (PROLE 2023)

Licencia Creative Commons

Resumen

Los análisis de dependencias de datos (ADD) responden a la pregunta: ¿qué partes del programa pueden influenciar el valor de esta variable? Estos análisis son comunes en herramientas como compiladores, depuradores y muchos otros análisis de software para determinar terminación, paralelizar automáticamente, depurar, optimizar, etc. Sabemos que en el caso general ADD es indecidible debido a la no-terminación: siempre es posible encontrar un programa para el que no podemos asegurar si la variable de interés es alcanzable (el programa podría divergir antes), y por tanto no podemos determinar si alguna parte del programa podría influenciar a esa variable. En enero del 2000, Thomas Reps probó la indecidibilidad de un ADD para programas que sí terminan, demostrando que la no-terminación no es la única causa fundamental de indecidibilidad. El ADD que Reps utilizó, sin embargo, era un análisis muy específico. Este trabajo utiliza y expande los resultados de Reps para determinar que existe una clase de ADDs (que incluye el propio ADD usado por Reps) que son indecidibles incluso para programas que sí terminan. Además, describimos qué características debe tener un lenguaje de programación para que los ADDs de esta clase sean indecidibles en el caso general.

Descripción

Acerca de Galindo, Carlos

Palabras clave

Análisis De Programas, Dependencias De Datos, Flujo De Datos, Decidibilidad
Página completa del ítem
Notificar un error en este artículo
Mostrar cita
Mostrar cita en BibTeX
Descargar cita en BibTeX