Authors: Giuseppe Mazzotta, Francesco Ricca, Mirek Truszczynski
Abstract: Answer Set Programming with Quantifiers (ASP(Q)) has been introduced to
provide a natural extension of ASP modeling to problems in the polynomial
hierarchy (PH). However, ASP(Q) lacks a method for encoding in an elegant and
compact way problems requiring a polynomial number of calls to an oracle in
$\Sigma_n^p$ (that is, problems in $\Delta_{n+1}^p$). Such problems include, in
particular, optimization problems. In this paper we propose an extension of
ASP(Q), in which component programs may contain weak constraints. Weak
constraints can be used both for expressing local optimization within
quantified component programs and for modeling global optimization criteria. We
showcase the modeling capabilities of the new formalism through various
application scenarios. Further, we study its computational properties obtaining
complexity results and unveiling non-obvious characteristics of ASP(Q) programs
with weak constraints.
Source: http://arxiv.org/abs/2408.07697v1
