2-ASP(Q) programs with weak constraints: Complexity and efficient implementation
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916050850807808 |
|---|---|
| author | Cuteri, Andrea Mazzotta, Giuseppe Ricca, Francesco |
| author_facet | Cuteri, Andrea Mazzotta, Giuseppe Ricca, Francesco |
| contents | 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. On the theoretical side, we provide a complete complexity characterization of the main computational tasks for 2-ASP(Q)^w programs, including tight completeness results and the analysis of nontrivial cases that have not been addressed in previous works. On the practical side, we introduce novel strategies for computing (optimal) quantified answer sets in the Casper system, that rely on a Counterexample-Guided Abstraction Refinement (CEGAR) technique tailored to ASP(Q). An experimental evaluation on hard benchmarks from different application domains shows that the proposed techniques are effective in practice. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_27338 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | 2-ASP(Q) programs with weak constraints: Complexity and efficient implementation Cuteri, Andrea Mazzotta, Giuseppe Ricca, Francesco Artificial Intelligence Computational Complexity Computation and Language Logic in Computer Science 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. On the theoretical side, we provide a complete complexity characterization of the main computational tasks for 2-ASP(Q)^w programs, including tight completeness results and the analysis of nontrivial cases that have not been addressed in previous works. On the practical side, we introduce novel strategies for computing (optimal) quantified answer sets in the Casper system, that rely on a Counterexample-Guided Abstraction Refinement (CEGAR) technique tailored to ASP(Q). An experimental evaluation on hard benchmarks from different application domains shows that the proposed techniques are effective in practice. |
| title | 2-ASP(Q) programs with weak constraints: Complexity and efficient implementation |
| topic | Artificial Intelligence Computational Complexity Computation and Language Logic in Computer Science |
| url | https://arxiv.org/abs/2605.27338 |