2-ASP(Q) programs with weak constraints: Complexity and efficient implementation
Andrea Cuteri, Giuseppe Mazzotta, Francesco Ricca
Read on arXiv →
Key claim
2-ASP(Q)^w effectively captures optimization problems.
This paper presents 2-ASP(Q)^w, a new fragment of Answer Set Programming that can handle optimization problems. The authors introduce effective strategies for computing quantified answer sets, validated through experiments on challenging benchmarks, demonstrating practical effectiveness.
In plain English
This paper presents 2-ASP(Q)^w, a new fragment of Answer Set Programming that can handle optimization problems. The authors introduce effective strategies for computing quantified answer sets, validated through experiments on challenging benchmarks, demonstrating practical effectiveness.
The introduction of 2-ASP(Q)^w and its application to optimization problems represents a meaningful extension of existing ASP frameworks.
The paper provides a complete complexity characterization and experimental evaluation, supporting its claims with solid evidence.
Deep reliability assessment
The methodology supports the complexity analysis and implementation of 2-ASPw(Q) programs, but the practical effectiveness of the proposed techniques may be overclaimed without extensive real-world testing.
Reproducibility
Yes, benchmarks and executables are available at https://osf.io/gmnjx.
Discussion questions
- How does the assumption of using CEGAR for 2-ASPw(Q) hold up against other potential optimization techniques?
- What are the practical implications for builders using 2-ASPw(Q) in real-world applications?
- What specific scenarios or benchmarks would falsify the claimed effectiveness of the proposed techniques?
Key figure
Figure 1 shows a cactus plot comparing the execution time of different systems on all instances.