实时正则表达式匹配
我们使用转移半群建立一种有限状态自动机的即时确定化的抽象,并展示了如何应用它来界定渐近性。我们呈现了足够导致确定自动机的多项式状态复杂性的代数和组合特性。我们发现的一个特例是,具有许多非确定性转换的自动机几乎总是适用于多项式复杂性的确定化。此外,我们将我们的思想扩展到加权有限状态自动机。
Aug, 2023
本文提出了一种改进的算法,它可以测试两个确定性或非确定性有限状态自动机的等价性,具有接近线性的最佳情况运行时间,并且与先前提出的算法之间存在关系。同时,我们还将这些算法与 Rutten 提出的最近的代数方法进行了比较。
Jul, 2009
介绍了一种用于处理非连贯现象的有限状态转换器的新技术,通过将正则表达式编译器重新应用到其自身的输出来实现,该算法称为编译替换, 并在马来语全干重复和阿拉伯语干部分插入上进行了演示。
Jun, 2000
该研究旨在探索将自然语言查询翻译成代表它们含义的正则表达式的任务。为了充分发挥神经模型的潜力,该研究提出了一种收集大规模的正则表达式和自然语言对的方法,并通过该模型实现了比之前最先进模型提升了 19.6% 的性能。
Aug, 2016
本研究旨在探讨不同复杂度的 Tomita 文法上,从常用的循环神经网络中提取确定有限状态自动机的性能表现。研究结果表明,随着底层文法复杂度的提高,大多数循环神经网络的提取性能逐渐降低。
Jan, 2018
通过训练循环神经网络(RNN)来学习识别正则形式语言时使用的内部表示,我们研究了一个简单的解码函数,其将该 RNN 的状态映射到该语言的最小确定性有限自动机(MDFA)的状态,进而探讨了 RNN 内部表示与有限状态自动机之间的强结构关系,解释了 RNN 识别正式语法结构的能力。
Feb, 2019
给出并分析了一种用于有效构建确定性有限自动机的算法,该算法旨在直接处理由流行的字节对编码技术生成的标记化文本,从而可以将许多现有的技术和算法应用于标记化案例,例如模式匹配、标记化词典的等价检查和以各种方式组合标记化语言。
May, 2024
从自然语言描述生成正则表达式(regexes)的新范 Paradigm InfeRE 通过逐步推理的方式生成 regexes,通过多个模型的采样输出来提高鲁棒性,优于先前的基线方法和基于树的生成方法 TRANX,具有提高 DFA@5 准确率的性能
Aug, 2023