24 de mayo de 2013

Escapando al no-determinismo

Mis disculpas por el "silencio de radio" que se ha visto últimamente en este blog. He estado terminando con los cursos donde debía dar clases, postulando para obtener financiación para el año próximo, y terminando algunas investigaciones.

Hoy enviamos con Gilles Dowek un resumen extendido a un workshop. Desde que me doctoré he estado trabajando en cálculos y lógicas no-deterministas, pero el objetivo siempre fue, y sigue siendo, no perder de vista la computación cuántica. Un primer paso, es pasar del no-determinismo a algo un poco más controlado: probabilístico (ya habrá tiempo más adelante para ir hacia un paso superior que es el caso cuántico).

En este trabajo mostramos una forma genérica de convertir un sistema de reescritura no-determinístico abstracto en un sistema probabilístico, y luego lo aplicamos a λ+, un cálculo lambda no-determinístico que desarrollamos anteriormente.

Lo que hacemos aquí es definir una medida de Lebesgue en el espacio de trazas de ejecución del sistema. La idea es definir cajas (boxes) que determinan ciertas trazas, y dejan las otras libres. De esa manera podemos definir fácilmente una medida sobre esas cajas, y luego extenderlo a cualquier ejecución mediante un recubrimiento por cajas.

El preprint puede descargarse de aquí: probas.pdf

Update: El paper fue aceptado en DCM. Más info aquí.