定向正则和无上下文语言
本文主要研究了凸语言的决策问题,对于由 DFA 表示的一个给定语言 L,我们可以在多项式时间内决定该语言 L 是否为前缀、后缀、因子或子串凸,但如果用 NFA 表示,这个问题则是 PSPACE 难问题。此外,还证明了该正则语言不是凸的情况下,最短单词的长度是有限的,并给出了紧上界。同时,本文还研究了几个凸语言的子类。
Aug, 2008
研究一种决策问题:给定两个有限单词的正则输入语言,判断是否存在第一阶可定义的分隔符;证明可以从识别输入语言的半群中提取充分信息并使用不动点计算以回答此问题,这产生了一个检查一阶可分离性的 EXPTIME 算法;进一步推广此技术以回答针对无限字的正则语言同样的问题,并得到一个可能的分隔符描述。
Feb, 2014
针对一类无上下文语法,研究了等价性的可决定性问题,证明了 Clark-congruential grammar 类中此问题是可决定的,同时考虑了如何检查 CFG 是否属于此类,并证明在给定 CFG 是 DCFG 的情况下此问题是可决的。
May, 2018
本文研究的问题是,在部分边缘方向已知的情况下,如何计算马尔科夫等价类中有向无环图的数量。我们发现,这个问题在一个有趣的实例类中是可固定参数可解的,因为我们建立了一个计数算法,它所需要的时间是该图大小的多项式,其次数不依赖于作为输入提供的附加边的数量。
Jun, 2022
本研究通过控制机制,定义了四种文法形式:PDAs 控制 PDAs 生成的语言,PDAs 控制 CFGs 生成的语言,CFGs 控制 PDAs 生成的语言和 CFG 控制 CFG 生成的语言,进一步精确定义了它们之间的等价关系,此外,提出了一种称为 PAA 的新型自动机形式,它从 CFG 控制 PDA 的角度出发生成语言。
Jun, 2023
本文广义了 Bar-Hille 构造,使其能够正确计算包含 epsilon 弧的自动机的交集,并证明该广义构造导致一个编码输入自动机和文法结构的文法,同时保留原始构造的渐近大小。
Sep, 2022
本文提出了一种改进的算法,它可以测试两个确定性或非确定性有限状态自动机的等价性,具有接近线性的最佳情况运行时间,并且与先前提出的算法之间存在关系。同时,我们还将这些算法与 Rutten 提出的最近的代数方法进行了比较。
Jul, 2009
本文通过对具有有限追赶特性的规则语言分类,提出了一族可决定性规则语言,研究了这些语言的复杂性,证明了具有有限追赶特性的规则语言扩展弱无环语言的表现力与弱无环语言相同,并且综合复杂性更高的规则语言一般比综合复杂性更低的规则语言更简洁。
Nov, 2014
本研究设计实验以探究生成式语言模型如何学习上下文无关文法,并发现了 Transformer 如何利用物理机制隐式地编码文法结构、形成类动态规划的 attention,并在处理语法错误时表现出的鲁棒性方面的相关拓展。
May, 2023