识别加权树相邻语言的高效算法
本研究研究了Vijay-Shanker和Weir(1994)形式主义下组合范畴语法(CCG)的解析复杂性。我们的主要结果是,在分析中,将语法的大小(而不仅仅是输入句子的长度)考虑进去时,该形式主义的任何解析算法最坏情况下需要指数时间。这与弱等价形式主义(如Tree-Adjoining Grammar (TAG))有所不同,对于这种形式主义,可以在与语法和输入句子的大小成多项式时间完成分析。我们的研究结果有助于更加深入地理解轻度上下文敏感语法的分类,并为寻找新的轻度上下文敏感版本的CCG提供信息。
Feb, 2017
本篇文章研究了如何用查询学习算法解决确定性上下文自由文法的拓扑结构问题,提出了一种基于多重树状自动机算法的结构明确概率上下文自由文法学习方法,这种方法既可以学习语法的拓扑结构又可以学习概率权重,同时还给出了相应的结构化成员查询和结构等价查询算法。
Mar, 2022
本文广义了Bar-Hille构造,使其能够正确计算包含epsilon弧的自动机的交集,并证明该广义构造导致一个编码输入自动机和文法结构的文法,同时保留原始构造的渐近大小。
Sep, 2022
本文基于加权树自动机提出了一种新的线性时间算法,用于子树核计算,具有输出敏感性、无序数与有序数适用性以及适用于任何增量树内核学习方法等优点,并在多种合成树语言数据集上进行了实验,结果显示出了该算法超过了现有方法。
Feb, 2023
本研究通过控制机制,定义了四种文法形式:PDAs控制PDAs生成的语言,PDAs控制CFGs生成的语言,CFGs控制PDAs生成的语言和CFG控制CFG生成的语言,进一步精确定义了它们之间的等价关系,此外,提出了一种称为PAA的新型自动机形式,它从CFG控制PDA的角度出发生成语言。
Jun, 2023
这篇论文通过退化系统的形式提供了Earley(1970)上下文无关解析算法的参考描述,其中包括了多种加速的方法。我们的展示包括从Earley的$O(N^3|G||R|)$到$O(N^3|G|)$的已知最坏情况运行时间改进,这在自然语言处理中出现的大型语法中是不可行的,它与语法G的二元化版本上的CKY算法的运行时间相匹配。在这里,N是句子长度,|R|是G中的产生式数目,|G|是这些产生式的总长度。我们还提供了一个版本,在将语法简洁地表示为单个有限状态自动机M时实现了O(N^3|M|)的运行时间(这部分是新颖的)。我们细致地处理了到半环权重退化的概括,像Stolcke (1995)那样预处理语法以消除退化循环,并进一步推广Stolcke的方法以计算句子前缀的权重。我们还提供了高效执行的实现细节,在预处理语法上,我们方法的半环权重版本具有与无权重方法相同的渐近运行时间和空间要求,包括在某些语法上在次立方时间内的运行时间。
Jul, 2023
该研究论文通过泛化之前的左角转换方法,支持半环加权产生规则,并提供了对可以移动的左角进行更精细控制的能力。该泛化的左角转换方法通过用右递归替换左递归,与猜测转换方法定义了等价的加权语言,同时在生成树结构上存在重要差异。除此之外,对GLCT、猜测转换和原始语法的输出之间的形式关系进行了几项技术结果的探讨,并在九种语言的语法中对GLCT的效率进行了实证研究。
Nov, 2023
通过比较现有的证明,本文从计算和证明论的角度对多上下文无关文法(MCFGs)实现平衡语言的分析进行了系统研究,得出结论认为现有的证明都不适用于解决这个实际目标,并进一步提供了一种全新、基本、极短的证明方式。最后与现有证明进行了比较分析,证明了提出的证明对于实现$O_2$的已验证解析算法是一个重大进展。
May, 2024
研究了基于L*风格学习算法针对max-plus半环上的加权自动机的主题,提出了一种理论修复并介绍了一种算法,该算法可以在一类max-plus半环上的加权语言中终止。
Jul, 2024