Eliminación de variables para predicados ocultos en Answer Set Programming

Abstract

[Resumen] Los sistemas de Answer Set Programming (ASP), que computan las soluciones de un problema codificado mediante reglas lógicas, evalúan los programas de forma bottom-up, a partir de las reglas generan todos los hechos posibles sobre el dominio. Si la consulta del usuario solo necesita un subconjunto de esos hechos, el resto del cómputo es cómputo innecesario que consume tiempo y recursos. La transformación Magic Sets aborda precisamente este problema, reescribiendo el programa para que solo se deriven los hechos relevantes para la consulta. Magic Sets no está implementada en Clingo, el solver ASP más utilizado en la actualidad, pero sí en DLV mediante el algoritmo Dynamic Magic Sets (DMS). Se estudia en este ttrabajo la aplicabilidad de Magic Sets a Clingo adaptando el algoritmo DMS de DLV, y lo evalúa experimentalmente sobre un conjunto de problemas, comparándolo con otros sistemas del estado del arte.

[Abstract] Answer Set Programming (ASP) systems, which compute the solutions of a problem encoded as logical rules, evaluate programs bottom-up, from the rules they generate every possible fact over the domain. When the user’s query only needs a subset of those facts, the rest of the computation is unnecesary computing time that also consumes resources. The Magic Sets transformation addresses precisely this problem, rewriting the program so that only the facts relevant to the query are derived. Magic Sets is not implemented in Clingo, the most widely used ASP solver today, but it is in DLV through the Dynamic Magic Sets (DMS) algorithm. This work studies the applicability of Magic Sets to Clingo by adapting DLV’s DMS algorithm, and evaluates it experimentally on a set of problems, comparing it against other state-of-the-art systems.