Quantifying over Optimum Answer Sets
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910791265943552 |
|---|---|
| author | Mazzotta, Giuseppe Ricca, Francesco Truszczynski, Mirek |
| author_facet | Mazzotta, Giuseppe Ricca, Francesco Truszczynski, Mirek |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_07697 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantifying over Optimum Answer Sets Mazzotta, Giuseppe Ricca, Francesco Truszczynski, Mirek Artificial Intelligence Computational Complexity Computation and Language 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. |
| title | Quantifying over Optimum Answer Sets |
| topic | Artificial Intelligence Computational Complexity Computation and Language |
| url | https://arxiv.org/abs/2408.07697 |