Jun, 2023

连接证明理论和知识表示：序列演算和具有存在规则的 Chase

PDF
TL;DR本文主要探讨了知识表示中重要的可决定性工具 ——Chase 算法与证明理论中的证明搜索算法之间的联系，特别是在一阶逻辑的 Gentzen 序列演算的推广中探究了在存在性规则的情况下 Chase 机制本质上与证明搜索相同，并通过证明搜索生成知识库的通用模型，该特征也与 Chase 算法相同。
chase algorithmsknowledge base queryingsequent calculiproof-searchdecidability
发现论文，激发创造
  • 追逐变种中的有界性特征

    研究论文探讨了基于本体的查询应答中的万有模型问题，特别关注存在规则边界问题，提出了一般性质并证明了一些经典的 chase 变体满足该性质，进而解决了这些变体的有限深度问题。

    Apr, 2020

  • Existential 规则的 k-Boundedness 问题

    该论文研究对于三种追赶算法变种，如何确定给定规则集的有界性问题是可决的。

    Oct, 2018

  • 带有有限 Chase 的存在规则语言：复杂度和表达能力

    本文通过对具有有限追赶特性的规则语言分类，提出了一族可决定性规则语言，研究了这些语言的复杂性，证明了具有有限追赶特性的规则语言扩展弱无环语言的表现力与弱无环语言相同，并且综合复杂性更高的规则语言一般比综合复杂性更低的规则语言更简洁。

    Nov, 2014

  • 线性存在规则的半遗忘追逐终止：实验研究

    本文主要针对线性存在规则和半盲 chase 问题，通过理论研究、算法实现及实验数据评估 Chase 算法的性能限制，以期理解影响加速 Chase 算法终止的参数，探索其在实际中的适用性，并揭示其性能限制。

    Mar, 2023

  • 存在规则的规范化：不是那么无害！

    该研究系统研究了存在性规则对于不同的追踪变体以及基于一阶逻辑的重写的 (chase (non-) termination and FO-rewritability) 影响，从而探讨了相关的开放性问题。

    Jun, 2022

  • 存在规则的无环概念及其在本体查询回答中的应用

    本文探讨了如何使用 chase 算法在存在规则的事实集上回答联合查询，介绍了两种新的不将模型扩展到不可数状态的无环性概念，展示了如何基于这些概念构造 OWl2 本体推理器，从而提供了在实践中如何实现这些系统的基本理论解释。

    Feb, 2014

  • 驯服无限追踪：在表达完整性约束下进行查询回答

    提出了大类元组生成依赖和相等生成依赖的追赶算法思想，并以受限语言的形式表现，证明了这种情况下查询的可决策性。给出了一些具体的限制模型，并将其应用于较常见的问题，并在问题求解的复杂度方面给出了确切的界限。

    Dec, 2012

  • 非均匀终止追逐：尺寸和复杂度

    通过应用线性化和简化技术，我们证明了追踪算法在具有保护元组生成依赖的规则本体语言中是可行的，具有多项式时间复杂度，追踪的结果大小是相对于数据库的线性。

    Apr, 2022

  • 通过触发器图实现知识库

    本文介绍了一种新型引擎，结合触发图的概念来实现知识库的材料化技术，解决了冗余计算的问题，并在实验中得到了显著的效率提升。

    Feb, 2021

  • 存在规则语言的模型论描述

    本研究旨在模型理论中建立存在规则语言的模型论特性，如嵌入依赖项，元组生成依赖项和线性依赖项，并确定它们的复杂度限制。

    Jan, 2020