提出新方法解决信念逻辑程序，效率提升三倍以上。
Solving Epistemic Logic Programs using Generate-and-Test with Propagation
- 基于生成与验证框架，引入传播信念后果的新生成器。
- 测试候选数减少指数级，仅增加线性开销。
- 实测速度提升3.3倍，解决91%更多实例，适合逻辑推理研究者。
本文提出一个通用的基于生成与验证的信念逻辑程序求解框架，可灵活搭配不同生成器和验证器，并证明了确保求解器正确性的充分条件。同时引入一种新生成器，通过传播信念后果显著减少需验证的候选解数量，仅带来线性额外开销。基于该理论实现的新求解器在知名基准测试中表现优异，相较现有方法实现约3.3倍加速，成功求解91%更多的实例。
原文摘要 · Abstract (English)
This paper introduces a general framework for generate-and-test-based solvers for epistemic logic programs that can be instantiated with different generator and tester programs, and we prove sufficient conditions on those programs for the correctness of the solvers built using this framework. It also introduces a new generator program that incorporates the propagation of epistemic consequences and shows that this can exponentially reduce the number of candidates that need to be tested while only incurring a linear overhead. We implement a new solver based on these theoretical findings and experimentally show that it outperforms existing solvers by achieving a ~3.3x speed-up and solving 91% more instances on well-known benchmarks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。