论文标题
认知逻辑程序的结构分解
Structural Decompositions of Epistemic Logic Programs
论文作者
论文摘要
认识论逻辑程序（ELP）是对标准答案集编程（ASP）的流行概括，为在语言中推理答案集提供了手段。这种富裕的形式主义的价格是高于计算复杂性的代价，达到了多项式层次结构的第四级。但是，与标准ASP相反，尚未进行针对障碍的专门研究。在本文中，我们给出了这一方向的首先结果，并表明可以在线性时间内解决中央ELP问题，以使ELPs以界面宽方面的形式表现出结构性。我们还提供了遵守这些界限的完整动态编程算法。最后，我们表明，将树宽应用于新颖的依赖性结构 - 基于认知文字 - 允许在典型的ELP求解程序中绑定ASP求解器调用的数量。
Epistemic logic programs (ELPs) are a popular generalization of standard Answer Set Programming (ASP) providing means for reasoning over answer sets within the language. This richer formalism comes at the price of higher computational complexity reaching up to the fourth level of the polynomial hierarchy. However, in contrast to standard ASP, dedicated investigations towards tractability have not been undertaken yet. In this paper, we give first results in this direction and show that central ELP problems can be solved in linear time for ELPs exhibiting structural properties in terms of bounded treewidth. We also provide a full dynamic programming algorithm that adheres to these bounds. Finally, we show that applying treewidth to a novel dependency structure---given in terms of epistemic literals---allows to bound the number of ASP solver calls in typical ELP solving procedures.
