ACLJun, 2023

控制层次中的收敛与多样性

PDF
TL;DR本研究通过控制机制，定义了四种文法形式：PDAs 控制 PDAs 生成的语言，PDAs 控制 CFGs 生成的语言，CFGs 控制 PDAs 生成的语言和 CFG 控制 CFG 生成的语言，进一步精确定义了它们之间的等价关系，此外，提出了一种称为 PAA 的新型自动机形式，它从 CFG 控制 PDA 的角度出发生成语言。
language hierarchytree-adjoining grammarscontrollable pushdown automataderivation controlformalism
发现论文，激发创造
  • 识别加权树相邻语言的高效算法

    提供了树连接语言、两级形式主义、半环加权版本、字符串求和算法和下推连接自动机的关键算法。

    Oct, 2023

  • TAG 与 CCG 的强等价性

    比较了树相邻语法（TAG）和组合范畴语法（CCG）对于字符串和树的表达能力，发现它们在树上的表达能力基本上是一致的，特别地，只要有限制条件，如 CCG 没有空字符串的词库条目和一阶规则的度数不超过 2，则其表达能力可以达到最大。

    May, 2022

  • $O_2$ 是多重上下文无关文法：一种易实现、易形式化的证明

    通过比较现有的证明，本文从计算和证明论的角度对多上下文无关文法 (MCFGs) 实现平衡语言的分析进行了系统研究，得出结论认为现有的证明都不适用于解决这个实际目标，并进一步提供了一种全新、基本、极短的证明方式。最后与现有证明进行了比较分析，证明了提出的证明对于实现 $O_2$ 的已验证解析算法是一个重大进展。

    May, 2024

  • 带权下推自动机算法

    本研究通过改进 Lang 算法，开发了直接处理加权下推自动机的新算法，可以更有效地运用于自然语言处理中，并能够在空间和时间效率上取得优化。

    Oct, 2022

  • 语言模型的物理学：第 1 部分，无上下文语法

    本研究设计实验以探究生成式语言模型如何学习上下文无关文法，并发现了 Transformer 如何利用物理机制隐式地编码文法结构、形成类动态规划的 attention，并在处理语法错误时表现出的鲁棒性方面的相关拓展。

    May, 2023

  • 依存语法和短语结构语法的形式化分析，特别考虑词序现象

    本文探讨了词汇在 MTT 和其他依赖型语言理论中的中心作用，并研究了基于上下文无关文法（CFGs）的语言理论中无法复制词汇作用的问题。我们介绍了树邻接语法（TAG）作为一个在词汇化 CFGs 过程中自然产生的系统，并将 TAG 语法与 MTM 直接进行比较，并通过讨论某些非投影结构的计算复杂性，提出了将词序的局部性定义纳入 MTT 的表层句法组成部分的方法。

    Oct, 1994

  • Clark-congruential 语言的决策问题

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

    May, 2018

  • 古典线性逻辑，流形和范畴语法

    使用经典乘性线性逻辑提出一种基于范畴语法的模型，其中单词由连通的、有标记的端点构成的元组表示为 Word cobordisms，这些对象可以组织成一类类似于拓扑 cobordisms 的范畴，作为线性 λ 演算和古典、直觉线性逻辑的模型。

    Nov, 2019

  • 定向正则和无上下文语言

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

    Jan, 2024

  • 具有潜变量的有向无环图的马尔科夫等价类刻画

    本文新增一套足以构建所有最大祖先图的马尔科夫等价类的公共尾巴箭头的定向规则，并提供了一组定向规则，用于识别马尔科夫等价类的公共性，特别是对于因果推断的实用性。

    Jun, 2012