A casual semantics for Logic Programming

Abstract

[Resumen] En esta tesis, extendemos algunas de las principales semánticas de programación lógica, de manera que la información causal asociada con un átomo sea incluida en los modelos de cada programa lógico. Técnicamente, nuestra aproximación consiste en una semántica multivaluada donde cada átomo está asociado con sus causas en lugar de con un simple valor de verdad, verdadero o falso. Estas causas están representadas por valores causales: conjuntos de gráficos incomparables entre sí que forman un retículo completamente distributivo. Los valores causales pueden ser útiles para proporcionar justificaciones que expliquen por que un átomo dado es cierto en un modelo. Sin embargo, la característica más interesante es que estos valores puedan ser inspeccionados en el cuerpo de las reglas del programa por un nuevo tipo de literal causal, lo que permite, por ejemplo, razonar con enunciados de la forma "A ha causado B:' En concreto, definimos semánticas causales que son extensiones de la leasl model, la well-founded model, la slable model y la answer sel semanlics y demostramos que, para varios de los problemas causales que investigamos, el razonamiento en estas semánticas no es computacionalmente más costoso que en sus correspondientes versiones estándar. También proporcionamos métodos y herramientas para el cálculo de las soluciones de diversas tareas de razonamiento bajo estas semánticas y mostramos cómo pueden ser útiles para la representación de algunos de los ejemplos tradicionales de la literatura. El apéndice e contiene un resumen extendido en castellano.[Abstract] In this dissertation, we extend some of the major Logic Programming semantics, so that causal information is included into the models of a program. Technically, our approach consists in a multivalued semantics where atoms are associated to their causes instead of just assigning them a truth value, true or false. These causes are represented by causal values: sets of pairwise incomparable graphs that form a completely distributive lattice. Causal values can be useful for providing justifications explaining why a given atom holds in a model, but it is perhaps more interesting that they can be inspected into the body of program rules by a new kind of causal literal, allowing, for instance, to reason with statements of the form “A has caused B.” In particular, we define causal semantics that are conservative extensions of the least model, the well-founded model, the stable model and the answer set semantics and show that, for several of the causal problems we investigate, reasoning under these semantics is computationally as hard as in their standard counterparts. We also provide methods and tools for computing reasoning tasks under these semantics and show how they can be useful for representing some traditional scenarios of the literature[Resumo] Nesta tese, ampliamos algunhas das principais semánticas da programación lóxica de tal xeito que a información causal asociada cun átomo sexa incluída nos modelos de cada programa. Tecnicamente, a nosa aproximación consiste nunha semántica multivaluada, ande cada átomo está asociado ás súas causas no canto dun simple valor de verdade, verdadeiro ou falso. Estas causas son representadas por valores causais: conxuntos de grafos incomparables entre eles que forman un retículo completamente distributivo. Os valores causais poden ser útiles para proporcionar xustificacións que expliquen por que un átomo dado é certo nun modelo. Sen embargo, a característica máis interesante da nasa aproximación é que estes valores poden ser inspeccionados no carpo das regras do programa mediante un novo tipo de literal causal, perrnitindo, por exemplo, razóar con enunciados da forma 11 A causou B:' En concreto, definimos semánticas causais que son extensións da least model, a wellfounded model, a s/able model e answer set seman/ics e amosamos que, para moitos dos problemas causais que temas investigado, as tarefas de razoamento nestas semántica non son computacionalmente máis custosas que nas correspondentes versións estándar. Tamén proporcionamos métodos e ferramentas para calcular as solucións de varias tarefas de razoamento sobre estas semánticas e amasamos como poden ser útiles para representar algúns dos exemplos tradicionais da literatura. O Apéndice O contén un resumo ampliado en galego.