The Complexity of Reasoning for Fragments of Autoepistemic Logic
The Complexity of Reasoning for Fragments of Autoepistemic Logic
复制标题
自我认知逻辑片段推理的复杂性
DOI：
10.1145/2159531.2159539
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
H. Vollmer
中科院分区：
文献类型：
--
作者：
N. Creignou;A. Meier;M. Thomas;H. Vollmer
自认知逻辑通过情态运算符L扩展命题逻辑。前面有一个φ的公式被认为是“相信的”。该逻辑是由摩尔在1985年引入的，用于对理想理性代理人的行为进行建模，并对他自己的信念进行推理。在这篇文章中，我们分析了自认知逻辑的所有布尔片段，关于扩张存在、勇敢推理和谨慎推理这三个最常见的决策问题的计算复杂性。作为第二个贡献，我们对检查给定公式集是否具有稳定展开的计算复杂性和对给定知识库的稳定展开数进行计数的计算复杂性进行了分类。我们将前面问题的最著名的Δ2p-上界改进为布尔层次的第二层的完备性。据我们所知，这是第一篇分析自认知逻辑计数问题的论文。
Autoepistemic logic extends propositional logic by the modal operatorL. A formulaφthat is preceded by anLis said to be “believed.” The logic was introduced by Moore in 1985 for modeling an ideally rational agent’s behavior and reasoning about his own beliefs. In this article we analyze all Boolean fragments of autoepistemic logic with respect to the computational complexity of the three most common decision problems expansion existence, brave reasoning and cautious reasoning. As a second contribution we classify the computational complexity of checking that a given set of formulae characterizes a stable expansion and that of counting the number of stable expansions of a given knowledge base. We improve the best knownΔ2p-upper bound on the former problem to completeness for the second level of the Boolean hierarchy. To the best of our knowledge, this is the first paper analyzing counting problem for autoepistemic logic.
登录
查看更多内容
DOI：
10.1142/s0129054110007258
发表时间：
2010
期刊：
Int. J. Found. Comput. Sci.
影响因子：
--
作者：
Henning Schnoor
通讯作者：
Henning Schnoor
影响因子：
0.5
作者：
Michael Thomas
通讯作者：
Michael Thomas
关于 logspace MOD 类的闭包属性的注释
DOI：
10.1016/s0020-0190(00)00091-0
发表时间：
2000
期刊：
Inf. Process. Lett.
影响因子：
--
作者：
U. Hertrampf;S. Reith;H. Vollmer
通讯作者：
H. Vollmer
DOI：
10.1007/bf01744287
发表时间：
1979
期刊：
Mathematical systems theory
影响因子：
--
作者：
H. R. Lewis
通讯作者：
H. R. Lewis
Logspace-MOD 类的结构和重要性
DOI：
10.1007/bfb0020812
发表时间：
1991
期刊：
Artif. Intell.
影响因子：
--
作者：
G. Buntrock;C. Damm;U. Hertrampf;C. Meinel
通讯作者：
C. Meinel