Enhancing and Applying Answer Set Programming: Lazy Constraints, Partial Compilation and Question Answering

By Bernardo Cuteri,
Università della Calabria
17 January 2019


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 efficient 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 first contribution, we study some cases in which classical
evaluation fails because of the so-called grounding bottleneck. In particular,
we first focus on cases in which the standard evaluation strategy is ineffective due to the grounding of problematic constraints. We approach the problem using custom propagators and lazy instantiators, proving empirically when this solution is effective, 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 sufficient conditions for identifying the rules that can be compiled in an approach that fits a propagator-based system architecture. An empirical analysis shows the performance benefits obtained by introducing (partial) compilation into ASP programs evaluation. To the best of our knowledge, this is the first 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.