Apr, 2023

有限宽度反模理论的一阶查询可决定性

PDF
TL;DR提出了一个通用的查询决策框架，基于计数模型的结构简单性，可以确定各种逻辑蕴涵问题（简称查询）的可决性，其中 Blumensath 的分区宽度作为一个特别强大的宽度度量提出，重点介绍存在规则的形式化，其中分区宽度的规则子域覆盖范式为一周围侧子域。
发现论文，激发创造
  • 存在规则的有限团宽集：朝着决定性、高表达性查询的通用准则迈进

    该研究通过引入 “有限团宽集合”（FCS）来寻求可决定本体论查询的一般性标准，FCS 是一种模型理论定义的规则集类，受到图论中团宽的启发，这一类规则集确保了一类子句共有查询（DaMSOQs）的蕴涵可决定性，它们吸收了合取查询（CQs）并且限制于元数为 2 的符号。

    Sep, 2022

  • 从基于宽度的模型检查到基于宽度的自动定理证明

    该研究提出了一种通用框架，将基于宽度的模型检查算法转换为用于测试具有有限宽度图类的图论猜想的算法，并显示了在树宽度为 $k$ 的所有图上验证图论猜想的算法，时间为 $ k^{O (1)}$ 双指数级。

    May, 2022

  • 利用树宽度进行认识逻辑程序的数量推理

    本篇论文介绍了一种利用图形方法和动态规划结合已有的搜索求解器来解决定量推理问题的新系统，可以有效地处理 Answer Set Programming 方法中 epistemic logic programs 的复杂问题。

    Aug, 2021

  • 超树分解与可处理查询

    本文研究了关于合取查询 (conjunctive queries) 的一些决策问题，发现针对无环或几乎无环查询的问题虽然一般来说是 NP 完全，但限制到这些查询中节点的树宽度和循环度是有界的，变得易于处理。针对查询的宽度这一最普遍的概念，我们证明没有多项式时间的算法可以高效地判断查询的宽度是否小于等于 k，而引入的超树分解概念和超树宽度则可以周旋这一难点，使得相应的问题变得可解。

    Dec, 1998

  • 基于树宽求解问题的高级工具和方法 - 扩展摘要

    本文主要研究了基于逻辑的问题及基于 treewidth 的方法和工具，并提出了一种新类型的问题降解方法，其中问题为有界 treewidth 的量化布尔公式（QBF）。结果表明，treewidth 是设计现代求解器时应考虑的一项重要的测量标准。

    Aug, 2022

  • 基于本体的有界团宽数据库查询

    本研究从参数复杂性角度研究了在有界团宽度的数据库上对本体中介查询 (OMQ) 的评估，研究了原子查询 (AQ)、连通查询 (CQ) 和连通查询的联合，发现所有 OMQ 问题都是固定参数线性 (FPL) 的，其参数是 OMQ 大小加上团宽度，我们的主要贡献是详细分析了运行时间对参数的依赖，展示了几个有趣的影响。

    May, 2022

  • 图形模型推理的复杂度

    本文研究图形单元中结构的限制及其与推理难度之间的关系，发现较低的树宽是确保推理可行性的唯一结构限制，即使是最优情况下的图结构，也不存在多项式时间复杂度的推理算法。

    Jun, 2012

  • 超越一阶逻辑的提升推理

    据我们展开的 C² 的领域扩展，任何 C² 句子在其关系受限于表示有向无环图、连通图、树（或有向树）、森林（或有向森林）时仍保持领域可提升，这提供了一个计算组合结构的通用框架。

    Aug, 2023

  • 具有传递性的一元否定片段的有限可满足性

    研究发现：在包含任意数量的传递关系的一元否定分段中，有限可满足性问题是可判定和 2-ExpTime 完全问题。此外，我们探讨了我们的基本逻辑的各种扩展的有限可满足性，特别是描述逻辑中已知的名称和角色层次概念的表达。

    Sep, 2018

  • 具有传递角色的表达能力描述逻辑中的有限查询回答

    该研究探讨了有限本体中介查询应答的问题，使用 DLs 描述逻辑中的联合，当仅考虑本体的有限模型时，研究 FOMQA 是相关的，本研究显示了 SOIF 的三个适当片段的 FOMQA 具有可决定性，这是基于模型的特定规律，开发了自动机决策程序。

    Aug, 2018