Aug, 2008

凸语言的决策问题

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

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

    Jan, 2024

  • Clark-congruential 语言的决策问题

    针对一类无上下文语法，研究了等价性的可决定性问题，证明了 Clark-congruential grammar 类中此问题是可决定的，同时考虑了如何检查 CFG 是否属于此类，并证明在给定 CFG 是 DCFG 的情况下此问题是可决的。

    May, 2018

  • CSP 二分猜想的证明

    该论文研究了基于约束满足问题的自然组合问题如何表达的问题，分类了可在多项式时间内解决和 NP 完全的子类，并从约束语言的角度提出了一个算法来解决约束满足问题。

    Apr, 2017

  • 极小观察上语言的复杂度

    本文研究了最小 DFA 的状态复杂度和 infimal prefix-closed 可观察超语言之间的关系，并在此基础上证明了无法用多项式时间算法计算该语言的 DFA，且提出了一种时间复杂度为 O (2^n) 的计算方法。

    Mar, 2017

  • 用一阶逻辑分离正则语言

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

    Feb, 2014

  • 离散优化中可处理的三角形和无交凸性

    研究了离散优化问题的计算复杂度，基于限制变量 - 值分配三元组的每个三角形的成本，发现最大匹配问题和联合胜者性质是唯一的可接受限制，同时提出了一种基于无交集分配的凸基数函数问题类，证明了其在满足交叉自由凸性的前提下为可解的。

    Jan, 2014

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

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

    Jun, 2015

  • 线性反问题的凸几何

    本文提出一个通用框架将简单性概念转化为凸惩罚函数，基于原子范数构建凸优化解，进而实现在限制线性信息下恢复简单模型。

    Dec, 2010

  • 利用一种非常简单的属性有效地推断 NFA

    本文研究了基于有限状态机和重写规则的形式语法学习，提出了一种基于 SAT 求解器的 NFA 自动机规模求解方法，并验证了该方法的高效性。

    Mar, 2023

  • 具有单调和凸约束条件的程序的属性和应用

    通过扩展正常逻辑编程的概念和结果，我们研究了具有单调和凸约束条件的程序的性质，这些结果为一些最近扩展的逻辑编程提供了抽象的概述，并应用这些结果进一步提出了通过伪布尔约束的通用求解器计算 lparse 程序稳定模型的方法，这种方法通常比 smodels 系统更快。

    Sep, 2011