2-ASP(Q) programs with weak constraints: Complexity and efficient implementation
The paper discusses 2-ASP(Q) programs with weak constraints, a significant area in Answer Set Programming. It provides a complete complexity characterization of computational tasks related to this class and introduces efficient strategies for computing quantified answer sets. Experimental evaluations demonstrate the effectiveness of the proposed techniques in practical applications.
- ▪The study focuses on 2-ASP(Q)^w, a fragment of ASP(Q) that addresses optimization problems up to the class Delta_3^P.
- ▪It offers a complete complexity characterization for the main computational tasks of 2-ASP(Q)^w programs.
- ▪Novel strategies for computing optimal quantified answer sets are introduced, utilizing a CEGAR technique tailored to ASP(Q).
Opening excerpt (first ~120 words) tap to expand
Computer Science > Artificial Intelligence arXiv:2605.27338 (cs) [Submitted on 26 May 2026] Title:2-ASP(Q) programs with weak constraints: Complexity and efficient implementation Authors:Andrea Cuteri, Giuseppe Mazzotta, Francesco Ricca View a PDF of the paper titled 2-ASP(Q) programs with weak constraints: Complexity and efficient implementation, by Andrea Cuteri and Giuseppe Mazzotta and Francesco Ricca View PDF HTML (experimental) Abstract:ASP(Q) extends Answer Set Programming (ASP) with Quantifiers over answer sets. In this paper we focus on the class of ASP(Q) programs with two quantifiers and weak constraints, denoted as 2-ASP(Q)^w. 2-ASP(Q)^w is a practically relevant fragment of ASP(Q) that is expressive enough to capture optimization problems up to the class Delta_3^P.
…
Excerpt limited to ~120 words for fair-use compliance. The full article is at arXiv cs.AI.
Discussion
0 commentsMore from arXiv cs.AI
