本文研究了由 Bertoni 等人和 Kondacs 和 Watrous 提出的控制语言 (CL-1QFAs) 和测量 - 多个(MM-1QFAs)1-way 量子有限自动机的等价性,给出了两种 1-way 有限自动机的等价性性质以及多项式时间算法。
Mar, 2007
通过训练循环神经网络(RNN)来学习识别正则形式语言时使用的内部表示,我们研究了一个简单的解码函数,其将该 RNN 的状态映射到该语言的最小确定性有限自动机(MDFA)的状态,进而探讨了 RNN 内部表示与有限状态自动机之间的强结构关系,解释了 RNN 识别正式语法结构的能力。
Feb, 2019
我们使用转移半群建立一种有限状态自动机的即时确定化的抽象,并展示了如何应用它来界定渐近性。我们呈现了足够导致确定自动机的多项式状态复杂性的代数和组合特性。我们发现的一个特例是,具有许多非确定性转换的自动机几乎总是适用于多项式复杂性的确定化。此外,我们将我们的思想扩展到加权有限状态自动机。
Aug, 2023
本文研究了一元量子有限自动机的两种不同模型:一种称为一次测量的量子有限自动机,另一种称为多次测量的量子有限自动机。针对一次测量的模型,我们限制其接受有界误差,证明了它可以解决自由群上的词问题。此外,我们还证明了 measure-many 自动机接受语言的几个封闭性质,并提出了一个新的必要条件。最后,我们展示了如何使用新的构造技术使分段可测试语言被 measure-many 量子有限自动机接受,同时也证明了 1 维量子有限自动机的接受能力比正则语言的能力更弱。
Mar, 1999
在过去的文献中,非均匀的多项式大小有限自动机被用来解决非均匀的承诺决策问题。我们重点关注非确定性有限自动机的变体,它们具有至多一个(无歧义的)、多项式多个(少量的)接受计算路径,或者无歧义 / 少量计算路径导致每个固定配置。当这些机器仅能进行单向头移动时,可以证明在没有未经证明的困难假设的情况下,其中一些变体在计算能力上与其他变体不同。至于限制在多项式有界长度的实例上的两向机器,双向多项式大小的非确定性有限自动机和多项式大小的无歧义有限自动机在计算能力上是等效的。
Nov, 2023
DFAMiner 是一种用于学习从一组标记样本中获取最小可分离确定有限自动机(DFA)的无主动学习工具。
May, 2024
本文研究有限状态自动机、正则表达式匹配、模式识别和指数级扩张问题,在复杂的正则语言类别中提出了理论和硬件解决方案,解决了网络入侵检测系统工作中的严重限制问题,并通过正确性和复杂性定理支持该解决方案。
本文广义了 Bar-Hille 构造,使其能够正确计算包含 epsilon 弧的自动机的交集,并证明该广义构造导致一个编码输入自动机和文法结构的文法,同时保留原始构造的渐近大小。
Sep, 2022
本文研究了基于有限状态机和重写规则的形式语法学习,提出了一种基于 SAT 求解器的 NFA 自动机规模求解方法,并验证了该方法的高效性。
Mar, 2023
本研究发现,当使用好的 MDP Buchi 自动机来代替确定性 Rabin 自动机时,可以更好地将 omega-regular 目标使用于模型无关的强化学习中,并且使用 Streett 自动机所得到的交替好的 MDP 自动机,可以比最小的非确定性 Buchi 自动机更加简洁。
May, 2022