Quantifying over Optimum Answer Sets

Giuseppe Mazzotta, Francesco Ricca, Mirek Truszczynski
8/14/2024
cs.AIcs.CCcs.CL

No confident code implementation found for this paper.

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 $Σ_n^p$ (that is, problems in $Δ_{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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Using ASP(Q) to Handle Inconsistent Prioritized Data

78% match2026

Generalizing Level Ranking Constraints for Monotone and Convex Aggregates

76% match2023

Answer Set Counting and its Applications

76% match2025

An efficient solver for ASP(Q)

74% match1 repo72023

FourierSAT: A Fourier Expansion-Based Algebraic Framework for Solving Hybrid Boolean Constraints

74% match1 repo122019

Machine Learning and Constraint Programming for Efficient Healthcare Scheduling

73% match2024

Cite this paper

@article{mazzotta2024quantifying,
  title  = {Quantifying over Optimum Answer Sets},
  author = {Giuseppe Mazzotta and Francesco Ricca and Mirek Truszczynski},
  year   = {2024},
  eprint = {2408.07697},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2408.07697v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2408.07697.svg)](https://codeofpaper.com/paper/2408.07697)

Discussion