Feb, 2014

用一阶逻辑分离正则语言

PDF
TL;DR研究一种决策问题：给定两个有限单词的正则输入语言，判断是否存在第一阶可定义的分隔符；证明可以从识别输入语言的半群中提取充分信息并使用不动点计算以回答此问题，这产生了一个检查一阶可分离性的 EXPTIME 算法；进一步推广此技术以回答针对无限字的正则语言同样的问题，并得到一个可能的分隔符描述。
发现论文，激发创造
  • 定向正则和无上下文语言

    给定一门语言，研究判断其是否为有向语言以及与理想分解和下闭集相关的基本问题，对于正则语言而言，该问题属于多项式时间复杂度；对于固定字母表大小的 NFAs 而言，该问题为 NL-complete；而对于上下文无关语言而言，其有向性问题则为 PSPACE-complete。

    Jan, 2024

  • 凸语言的决策问题

    本文主要研究了凸语言的决策问题，对于由 DFA 表示的一个给定语言 L，我们可以在多项式时间内决定该语言 L 是否为前缀、后缀、因子或子串凸，但如果用 NFA 表示，这个问题则是 PSPACE 难问题。此外，还证明了该正则语言不是凸的情况下，最短单词的长度是有限的，并给出了紧上界。同时，本文还研究了几个凸语言的子类。

    Aug, 2008

  • 使用传递性和线性排序数据进行查询回答

    本研究研究了涉及强约束语言的蕴涵问题，如前沿守卫存在规则，并对一组特殊的关系施加额外的语义限制。我们考虑将关系限制为传递性、将一个关系的传递闭包限制为另一个关系、将关系限制为线性顺序。我们提出了一些自然的守卫性变体，以使推理在每种情况下具有可决定性，并确定了相应决策问题的复杂度。最后，我们证明了这些条件的轻微变化会导致不可决定性问题。

    Feb, 2022

  • 有限闭包系统中的极大闭集和半空间分离

    该论文讨论了抽象闭包系统中的半空间分离问题，并提出了一种基于贪心算法的方法来解决这一问题，并在子集包含关系的情况下进行了应用。

    Jan, 2020

  • 在大型有序字母表上学习正则语言

    研究使用有限分区的元素标记过渡的通用模型，在该模型中扩展了 Angluin 的 L * 算法以学习正则语言，并将该算法扩展到部分有序字母表上。

    Jun, 2015

  • 正则语言等价性检查

    本文提出了一种改进的算法，它可以测试两个确定性或非确定性有限状态自动机的等价性，具有接近线性的最佳情况运行时间，并且与先前提出的算法之间存在关系。同时，我们还将这些算法与 Rutten 提出的最近的代数方法进行了比较。

    Jul, 2009

  • 安全和协安全语言的一阶逻辑特征

    本文介绍了一种 FO-TLO 的片段 SafetyFO 和該兩個片段的對偶 coSafetyFO，它們在經濟安全和反應綜合方面的表現完全適合於 LTL 可定義的經濟安全和反應綜合語言，這一结果充分填補了 LTL 片段的特性的一些空白。

    Sep, 2022

  • 具有外延原子的无限公式的稳定模型

    该论文通过将内涵和外延原子区分，并将一阶公式的对称分裂定理推广到无穷公式，增强了无穷析取和合取命题的稳定模型定义，并用于推理。

    Aug, 2016

  • 一维均匀片段

    论文探讨了一维统一片段（U1）的性质，以及 U1 与适应更高元关系的描述逻辑（DLR_reg）的关系，并定义了一个描述逻辑版本的 U1 变体，并证明了与 U1 和其他相关逻辑的表现力有关的一系列新结果。

    Apr, 2016

  • 一阶逻辑与一阶单调逻辑重合

    研究图的逻辑和表达能力之间的关系，发现当且仅当图的树深度有限时，一阶逻辑和单调二阶逻辑在图的各类子集上具有相同的表达能力，在仅闭合于诱导子图的类上展示了类似的结果。

    Apr, 2012