Séminaire de Francesco Ricca - University of Calabria, Italy
Modeling and Solving Problems in the Polynomial Hierarchy with ASP(Q)16 févr. 2023 - 14:00
Answer Set Programming (ASP) is a logic programming paradigm featuring a purely declarative language with comparatively high modeling capabilities. Indeed, ASP can model problems in NP in a compact and elegant way. However, modeling problems beyond NP with ASP is known to be complicated, on the one hand, and limited to problems in ΣP2 on the other. Inspired by the way Quantified Boolean Formulas extend SAT formulas to model problems beyond NP, we proposed an extension of ASP that introduces quantifiers over stable models of programs. We name the new language ASP with Quantifiers (ASP(Q)). Arguably, ASP(Q) allows one to model problems in the Polynomial Hierarchy in a direct way, providing an elegant expansion of ASP beyond the class NP. In this seminar we overview ASP and ASP(Q), show a number of modelling examples to highlight ASP(Q) modeling capabilities. Moreover we describe the working principles of qasp an implementation of ASP(Q). qasp is a modular ASP(Q) solver that translates a quantified ASP program together with a given data instance into a Quantified Boolean Formula (QBF) to be solved by any QBF solver.