Browsing by Author "Ricca, Francesco"

Now showing 1 - 4 of 4

Computational tasks in answer set programming: algorithms and implementation
(2014-12-01) Dodaro, Carmine; Leone, Nicola; Ricca, Francesco
L’Answer Set Programming (ASP) è un paradigma di programmazione dichiarativa basato sulla semantica dei modelli stabili. L’idea alla base di ASP è di codificare un problema computazionale in un programma logico i cui modelli stabili, anche detti answer set, corrispondono alle soluzioni del problema. L’espressività di ASP ed il numero crescente delle sue applicazioni hanno reso lo sviluppo di nuovi sistemi ASP un tema di ricerca attuale ed importante. La realizzazione di un sistema ASP richiede di implementare soluzioni efficienti per vari task computazionali. Questa tesi si occupa delle problematiche relative alla valutazione di programmi proposizionali, ed in particolare affronta i task di model generation, answer set checking, optimum answer set search e cautious reasoning. La combinazione dei primi due task corrisponde alla computazione degli answer set. Infatti, il task di model generation consiste nel generare dei modelli del programma in input, mentre il task di answer set checking ha il compito di verificare che siano effettivamente modelli stabili. Il primo task è correlato alla risoluzione di formule SAT, ed è implementato -nelle soluzioni moderne- con un algoritmo di backtracking simile al Conflict-Driven Clause Learning (CDCL); il secondo è risolto applicando una riduzione al problema dell’insoddisfacibilità di una formula SAT. In presenza di costrutti di ottimizzazione l’obiettivo di un sistema ASP è l’optimum answer set search, che corrisponde a calcolare un answer set che minimizza il numero di violazioni dei cosiddetti weak constraint presenti nel programma. Il cautious reasoning è il task principale nelle applicazioni dataoriented di ASP, e corrisponde a calcolare un sottoinsieme degli atomi che appartengono a tutti gli answer set di un programma. Si noti che tutti questi task presentano una elevata complessità computazionale. I contributi di questa tesi sono riassunti di seguito: (I) è stato studiato il task di model generation ed è stata proposta per la sua risoluzione una combinazione di tecniche che sono state originariamente utilizzate per risolvere il problema SAT; (II) è stato proposto un nuovo algoritmo per l’answer set checking che minimizza l’overhead dovuto all’esecuzione di chiamate multiple ad un oracolo co-NP. Tale algoritmo si basa su una strategia di valutazione incrementale ed euristiche progettate specificamente per migliorare l’efficienza della risoluzione di tale problema; (III) è stata proposta una famiglia di algoritmi per il calcolo di answer set ottimi di programmi con weak constraint. Tali soluzioni sono state ottenute adattando algoritmi proposti per risolvere il problema MaxSAT; (IV) è stato introdotto un nuovo framework di algoritmi anytime per il cautious reasoning in ASP che estende le proposte esistenti ed include un nuovo algoritmo ispirato a tecniche per il calcolo di backbone di teorie proposizionali. Queste tecniche sono state implementate in wasp 2, un nuovo sistema ASP per programmi proposizionali. L’efficacia delle tecniche proposte e l’efficienza del nuovo sistema sono state valutate empiricamente su istanze utilizzate nella competizioni per sistemi ASP e messe a disposizione sul Web.
Enhancing and Applying Answer Set Programming: Lazy Constraints, Partial Compilation and Question Answering
(2019-01-17) Cuteri, Bernardo; Leone, Nicola; Ricca, Francesco
This work is focused on Answer Set Programming (ASP), that is an expressive formalism for Knowledge Representation and Reasoning. Over time, ASP has been more and more devoted to solving real-world problems thanks to the availability of e cient systems. This thesis brings two main contributions in this context: (i) novel strategies for improving ASP programs evaluation, and (ii) a real-world application of ASP to Question Answering in Natural Language. Concerning the rst contribution, we study some cases in which classical evaluation fails because of the so-called grounding bottleneck. In particular, we rst focus on cases in which the standard evaluation strategy is ine ective due to the grounding of problematic constraints. We approach the problem using custom propagators and lazy instantiators, proving empirically when this solution is e ective, which is an aspect that was never made clear in the existing literature. Despite the development of propagators can be effective, it has two main disadvantages: it requires deep knowledge of the ASP systems, and the resulting solution is not declarative. We propose a technique for overcoming these issues which we call program compilation. In our approach, the propagators for some of the logic rules (not only for the constraints) of a program are generated automatically by a compiler. We provide some su cient conditions for identifying the rules that can be compiled in an approach that ts a propagator-based system architecture. An empirical analysis shows the performance bene ts obtained by introducing (partial) compilation into ASP programs evaluation. To the best of our knowledge, this is the rst work on compilation-based techniques for ASP. Concerning the second part of the thesis, we present the development of a Natural Language Question Answering System whose core is based on ASP. The proposed system gradually transforms input questions into SPARQL queries that are executed on an ontological knowledge base. The system integrates several state-of-the NLP models and tools with a special focus on the Italian language and the Cultural Heritage domain. ASP is used to classify questions from a syntactical point of view. The resulting system is the core module of the PIUCULTURA project, funded by the Italian Ministry of Economic Development, that has the aim to devise a system for promoting and improving the fruition of Cultural Heritage.
Integrated development environment for answer set programming
(2012-11-30) Reale, Kristian; Leone, Nicola; Ricca, Francesco
Answer Set Programming (ASP) is a truly-declarative programming paradigm proposed in the area of non-monotonic reasoning and logic programming. The successful application of ASP in a number of advanced projects, has renewed the interest in ASP-based systems for developing real-world applications. Nonethe- less, to boost the adoption of ASP-based technologies in the scientific commu- nity and especially in industry, it is important to provide effective programming tools, supporting the activities of researchers and implementors, and simplifying user interactions with ASP solvers. In the last few years, several tools for ASP- program development have been proposed, including (more or less advanced) editors and debuggers. However, ASP still lacks an Integrated Development Environment (IDE) supporting the entire life-cycle of ASP development, from (assisted) programs editing to application deployment. In this thesis we present ASPIDE, a comprehensive IDE for ASP. It inte- grates a cutting-edge editing tool (featuring dynamic syntax highlighting, on- line syntax correction, auto-completion, code-templates, quick-fixes, refactoring, etc.) with a collection of user-friendly graphical tools for program composi- tion, debugging, profiling, database access, solver execution configuration and output-handling. A comprehensive feature-wise comparison with existing environments for developing logic programs is also reported in this thesis, which shows that ASPIDE is a step forward in the present state of the art of tools for ASP programs development.
Parallel evaluation of ASP programs:techniques and implementation
(2011-11-30) Sirianni, Marco; Ricca, Francesco; Leone, Nicola
Answer Set Programming (ASP) is a purely declarative programming paradigm based on nonmonotonic reasoning and logic programming. The idea of ASP is to represent a given computational problem by a logic program such that its answer sets correspond to solutions, and then, use an answer set solver to find such solutions. The ASP language is very expressive and allows the representation of high-complexity problems (i.e., every problem in the second level of the polynomial hierarchy); unfortunately, the expressive power of the language comes at the price of an elevated cost of answer set computation. Even if this fact has initially discouraged the development of ASP system, nowadays several implementations are available, and the interest for ASP is growing in the scientific community as well as in the field of industry. In the last few years, significant technological enhancements have been achie- ved in the design of computer architectures, with a move towards the adoption of multi-core microprocessors. As a consequence, Symmetric Multi-Processing (SMP) has become available even on non-dedicated machines. Indeed, at the time of writing, the majority of computer systems and even laptops are equipped with (at least one) dual-core processor. However, in the ASP context, the avail- able systems were not designed to exploit parallel hardware; thus significant improvements can be obtained by developing ASP evaluation techniques that allow the full exploitation of the computational resources offered by modern hardware architectures. The evaluation of ASP programs is traditionally carried out in two steps. In the first step an input program P undergoes the so-called instantiation process, which produces a program P0 semantically equivalent to P but not containing any variable; in turn, P0 is evaluated by using a backtracking search algorithm in the second step. The aim of this thesis is the design and the assessment of a number of par- allel techniques devised for both steps of the evaluation of ASP programs. In particular, a three-level parallel instantiation technique is presented for improv- ing the efficiency of the instantiation process which might become a bottleneck in common situations, especially when huge input data has to been dealt with. Moreover, a parallel multi-heuristics search algorithm and a parallel lookahead technique have been conceived for optimizing the second phase of the evaluation. The mentioned parallel techniques has been implemented in the state-of-the- art ASP system DLV. An extensive experimental analysis has been carried out in order to assess the performance of the implemented prototypes. Experimental results have confirmed the efficiency of the implementation and the effectiveness of those techniques.