Una semántica basada en juegos para la programación lógica rebatible

Abstract

El objetivo principal de esta tesis es estudiar la teoría de prueba de la Programación en Lógica Rebatible (P.L.R.) y brindar una caracterización declarativa equivalente. La P.L.R. es una herramienta valiosa para la representación de conoci-miento tentativo, incierto y potencialmente inconsistente, que provee un mecanismo de inferencia basado en los sistemas argumentativos. En los últimos años, los sistemas argumenta-tivos han comenzado a ser utilizados en diversos campos de aplicación como la web y sistemas multiagentes. En esta Tesis se presenta una caracterización declarativa basada en la teoría de modelos y en la noción de juegos, de la P.L.R.. La semántica declarativa trivaluada desarrollada, que se denomi-na GS, es sensata y completa con respecto a la teoría de prueba de P.L.R.. Como punto intermedio, se brinda una forma-lización declarativa equivalente de la estructura de argumento y se circunscribe el conjunto de todos los posibles argumen-tos a favor y en contra que pueden construirse para una con-sulta dada bajo un programa lógico rebatible. A partir de los resultados obtenidos, se realizó un estudio de la complejidad computacional de la P.L.R.. En este sentido, se definieron pro-blemas de decision relevantes con respecto a los juegos bajo el contexto de un programa lógico rebatible y se calculó la complejidad computacional de la existencia de argumentos y contraargumentos. Asimismo, considerando el nexo existente entre la Programación en Lógica y las bases de datos deduc-tivas se definieron las complejidades de datos, expresión y combinada, y se establecio una cota superior para la com-plejidad de datos. Dichos resultados nos dan un indicio para determinar el poder expresivo de la P.L.R..

The main goal of this thesis is to study Defeasible Logic Programming (DeLP) proof theory and to provide an equivalent declarative characterization. DeLP is a valued tool for repre-senting tentative, uncertain, and potentially inconsistent knowledge, that provide an inference mechanism based on argumentative systems. In the last decade, argumentative systems have been used in different applications fields, such as the web and multiagent systems. In this thesis we present a declarative caracterization based in model theory and in game concepts of Defeasible Logic Programming (DeLP). The trivalued declarative semantics developped, noted GS, is sound and complete with respect to DeLP proof theory. As an intermediate point, we provide an equivalent declarative for-malization of argument structure and we circunscribe the set of all possible arguments for and against that can be cons-tructed for a query under a defeasible logic program. From the results we have obtained, we carry out an study of DeLP computational complexity. We have defined relevants decision problems with respect to the construction of a game under a defeasible logic program and we calculate the computational complexity of arguments and conterargument existence. Furthermore, considering the link between Logic Programmning and deductive data bases we have defined data complexity, expression complexity and combined complexity and we have established a upper bound for data complexity. These results give us a trace for determining DeLP expressive power.