Consequence-based and fixed-parameter tractable reasoning in description logics
Consequence-based and fixed-parameter tractable reasoning in description logics
复制标题
描述逻辑中基于结果和固定参数的易处理推理
DOI：
10.1016/j.artint.2014.01.002
复制
发表时间：
2014
影响因子：
14.4
通讯作者：
Simancík F
中科院分区：
文献类型：
--
作者：
Simancík F
在本文中，我们研究了目前常用的基于描述逻辑本体的包含推理的基于结果的算法，提出了以下新颖的结果。首先，我们提出了一个非常通用的基于结果的推理算法，该算法可以实例化，以获取已知算法的本质特征。其次，我们使用该算法开发了一个新的框架，用于对描述逻辑本体中包含推理的复杂性进行定量和参数分析。我们的方法基于广告合成的概念--一种类似图形的结构，粗略地说，它总结了本体推理过程中相关的模型。我们将宽度和长度确定为决定组合推理“水平”的分解参数。我们证明了，当被分解参数化时，我们的基于结果的算法在固定参数的宽度和长度上是可处理的。第三，我们简要讨论了长度和宽度如何表征Tableau算法的行为。第四，我们证明了现有本体的宽度和长度都相当小，我们认为这解释了基于结果的算法在实践中的良好性能。从而为本体推理器的实际实现奠定了良好的基础，也为推理器的性能分析提供了一种方法。
In this paper we investigate the consequence-based algorithms that are nowadays commonly used for subsumption reasoning with description logic ontologies, presenting the following novel results. First, we present a very general consequence-based reasoning algorithm that can be instantiated so as to capture the essential features of the known algorithms. Second, we use this algorithm to develop a novel framework for a quantitative and parametric analysis of the complexity of subsumption reasoning in description logic ontologies. Our approach is based on the notion of adecomposition—a graph-like structure that, roughly speaking, summarizes the models relevant during ontology reasoning. We identifywidthandlengthas decomposition parameters that determine the “level” of combinatorial reasoning. We prove that, when parameterized by a decomposition, our consequence-based algorithm runs in time that is fixed-parameter tractable in width and length. Third, we briefly discuss how length and width characterize the behavior of tableau algorithms. Fourth, we show that the width and length of existing ontologies are reasonably small, which, we believe, explains the good performance of consequence-based algorithms in practice. We thus obtain a sound foundation for a practical implementation of ontology reasoners, as well as a way to analyze the reasoners' performance.
登录
查看更多内容
DOI：
10.1016/j.websem.2011.12.007
发表时间：
2012-07
期刊：
J. Web Semant.
影响因子：
--
作者：
Birte Glimm;Ian Horrocks;B. Motik;Rob Shearer;G. Stoilos
通讯作者：
Birte Glimm;Ian Horrocks;B. Motik;Rob Shearer;G. Stoilos
DOI：
10.1007/11916277_16
发表时间：
2006-11
期刊：
--
影响因子：
--
作者：
B. Motik;U. Sattler
通讯作者：
B. Motik;U. Sattler
用于使用健全全局缓存的 ExpTime Tableaux
DOI：
--
发表时间：
2013
期刊：
Journal of automated reasoning
影响因子：
--
作者：
R. Goré;Linh Anh Nguyen
通讯作者：
Linh Anh Nguyen
极具表现力的描述逻辑中推理的数据复杂性
DOI：
--
发表时间：
2005
期刊：
International Joint Conference on Artificial Intelligence
影响因子：
--
作者：
U. Hustadt;B. Motik;U. Sattler
通讯作者：
U. Sattler
影响因子：
2.5
作者：
Grau, Bernardo Cuenca;Horrocks, Ian;Sattler, Ulrike
通讯作者：
Sattler, Ulrike