提出高效精确与近似答案集计数方法，提升逻辑推理效率。
Answer Set Counting and its Applications
- 用紧凑编码实现精确计数，比现有方法更快
- 近似计数结合高斯消元，速度优于传统方法
- 适用于网络可靠性评估等实际场景
本文聚焦于答案集编程（ASP）中的答案集计数问题，研究了精确与近似方法。我们开发了精确计数器sharpASP，采用紧凑的命题公式编码，显著提升了效率，相比现有方法在多个基准测试中表现更优。此外，提出近似计数器ApproxASP，基于哈希技术并集成高斯消元法至ASP求解器clingo。作为实际应用，使用ApproxASP进行网络可靠性估计，性能优于传统可靠性估算器及#SAT方法。
原文摘要 · Abstract (English)
We have focused on Answer Set Programming (ASP), more specifically, answer set counting, exploring both exact and approximate methodologies. We developed an exact ASP counter, sharpASP, which utilizes a compact encoding for propositional formulas, significantly enhancing efficiency compared to existing methods that often struggle with inefficient encodings. Our evaluations indicate that sharpASP outperforms current ASP counters on several benchmarks. In addition, we proposed an approximate ASP counter, named ApproxASP, a hashing-based counter integrating Gauss-Jordan elimination within the ASP solver, clingo. As a practical application, we employed ApproxASP for network reliability estimation, demonstrating superior performance over both traditional reliability estimators and #SAT-based methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。