通过缩小事实域提升ASP求解效率，显著降低接地耗时与文件大小。
Diminution: On Reducing the Size of Grounding ASP Programs
- 从赫伯兰德论域中选取子集生成精简接地程序
- 平均缩短70%接地时间，文件大小减少85%
- 适配现有求解器，适用于各类逻辑编程任务
答案集编程（ASP）常受制于接地瓶颈：庞大的赫伯兰德论域会产生过大的接地程序，导致求解困难。现有方法多依赖启发式策略，缺乏系统性。本文提出‘缩减’（diminution）概念，即在接地前选择赫伯兰德论域的子集生成更小的接地程序。我们给出了缩减的严格定义，分析其关键性质，并研究其识别复杂度。通过特定编码，可利用现成的ASP求解器评估候选子集。该方法通过领域谓词无缝集成至现有接地器。在五个基准上的实验表明，采用本文策略选出的缩减方案，平均使接地时间减少70%，接地文件大小最多下降85%。结果证明，利用缩减是缓解ASP接地瓶颈的一种稳健且通用的方法。
原文摘要 · Abstract (English)
Answer Set Programming (ASP) is often hindered by the grounding bottleneck: large Herbrand universes generate ground programs so large that solving becomes difficult. Many methods employ ad-hoc heuristics to improve grounding performance, motivating the need for a more formal and generalizable strategy. We introduce the notion of diminution, defined as a selected subset of the Herbrand universe used to generate a reduced ground program before solving. We give a formal definition of diminution, analyze its key properties, and study the complexity of identifying it. We use a specific encoding that enables off-the-shelf ASP solver to evaluate candidate subsets. Our approach integrates seamlessly with existing grounders via domain predicates. In extensive experiments on five benchmarks, applying diminutions selected by our strategy yields significant performance improvements, reducing grounding time by up to 70% on average and decreasing the size of grounding files by up to 85%. These results demonstrate that leveraging diminutions constitutes a robust and general-purpose approach for alleviating the grounding bottleneck in ASP.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。