提出2-ASP(Q)带弱约束的求解方法，有效处理高阶优化问题。
2-ASP(Q) programs with weak constraints: Complexity and efficient implementation
- 基于CEGAR框架设计新求解策略
- 可处理达Delta_3^P类优化问题
- 适合逻辑编程与复杂优化场景
ASP(Q)在答案集编程中引入了对答案集的量词。本文聚焦于包含两个量词和弱约束的ASP(Q)程序，记为2-ASP(Q)^w。该类程序是ASP(Q)中具有实际意义的片段，表达能力足以刻画高达Delta_3^P类的优化问题。理论上，本文给出了2-ASP(Q)^w主要计算任务的完整复杂度刻画，包括紧致的完备性结果以及此前未被研究的非平凡情形分析。实践上，我们在Casper系统中引入新型策略，基于专为ASP(Q)定制的反例引导抽象精化（CEGAR）技术来计算（最优）量化答案集。在多个应用领域的硬基准测试上，实验表明所提方法在实践中高效有效。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。