Aug, 2023

有限状态自动机的即时确定化分析

PDF
TL;DR我们使用转移半群建立一种有限状态自动机的即时确定化的抽象，并展示了如何应用它来界定渐近性。我们呈现了足够导致确定自动机的多项式状态复杂性的代数和组合特性。我们发现的一个特例是，具有许多非确定性转换的自动机几乎总是适用于多项式复杂性的确定化。此外，我们将我们的思想扩展到加权有限状态自动机。
on-the-fly determinizationfinite-state automatatransition monoidsasymptoticsstate complexity
发现论文，激发创造
  • 从不确定性 Büchi 和 Streett 自动机到确定性 Parity 自动机

    本研究重新审视了 Safra 关于无限词汇自动机确定性构造的技术，并通过减少状态数和引入奇偶数接受条件等方法，提出了新的构造方式。通过使用我们构造出的更小的确定性自动机，可以降低关于树自动机、CTL * 可满足性、逻辑规范的实现和综合等领域的上限，并且能够使用更高效的算法。

    May, 2007

  • 非均匀多项式大小的非确定有限自动机的非模糊性和有限性

    在过去的文献中，非均匀的多项式大小有限自动机被用来解决非均匀的承诺决策问题。我们重点关注非确定性有限自动机的变体，它们具有至多一个（无歧义的）、多项式多个（少量的）接受计算路径，或者无歧义 / 少量计算路径导致每个固定配置。当这些机器仅能进行单向头移动时，可以证明在没有未经证明的困难假设的情况下，其中一些变体在计算能力上与其他变体不同。至于限制在多项式有界长度的实例上的两向机器，双向多项式大小的非确定性有限自动机和多项式大小的无歧义有限自动机在计算能力上是等效的。

    Nov, 2023

  • 正则语言等价性检查

    本文提出了一种改进的算法，它可以测试两个确定性或非确定性有限状态自动机的等价性，具有接近线性的最佳情况运行时间，并且与先前提出的算法之间存在关系。同时，我们还将这些算法与 Rutten 提出的最近的代数方法进行了比较。

    Jul, 2009

  • 对无限字母表上的寄存式自动机和转换器的单次使用限制

    该论文研究了对无限字母的寄存器自动机和转换器的单次使用限制，通过引入单次使用的函数的抽象概念并定义所有讨论的单次使用模型，论文提出了关于单次使用限制的一致性叙述，并介绍和研究了局部半群转导和局部有理半群转导的代数模型。

    Jun, 2024

  • 利用一种非常简单的属性有效地推断 NFA

    本文研究了基于有限状态机和重写规则的形式语法学习，提出了一种基于 SAT 求解器的 NFA 自动机规模求解方法，并验证了该方法的高效性。

    Mar, 2023

  • 1-Way 量子有限自动机的特征

    本文研究了一元量子有限自动机的两种不同模型：一种称为一次测量的量子有限自动机，另一种称为多次测量的量子有限自动机。针对一次测量的模型，我们限制其接受有界误差，证明了它可以解决自由群上的词问题。此外，我们还证明了 measure-many 自动机接受语言的几个封闭性质，并提出了一个新的必要条件。最后，我们展示了如何使用新的构造技术使分段可测试语言被 measure-many 量子有限自动机接受，同时也证明了 1 维量子有限自动机的接受能力比正则语言的能力更弱。

    Mar, 1999

  • 实时正则表达式匹配

    本文研究有限状态自动机、正则表达式匹配、模式识别和指数级扩张问题，在复杂的正则语言类别中提出了理论和硬件解决方案，解决了网络入侵检测系统工作中的严重限制问题，并通过正确性和复杂性定理支持该解决方案。

    Aug, 2023

  • 有限状态非连接形态

    介绍了一种用于处理非连贯现象的有限状态转换器的新技术，通过将正则表达式编译器重新应用到其自身的输出来实现，该算法称为编译替换， 并在马来语全干重复和阿拉伯语干部分插入上进行了演示。

    Jun, 2000

  • 解释有限状态自动机用于序列数据

    本文研究了 Automaton 模型的可解释性问题，通过修改状态合并方法来学习变量的有限状态自动机，提出了关键特性的概念，进而应用于各类监督和无监督分类、聚类等涉及到顺序数据的问题。

    Nov, 2016

  • 有限时间范围下基于混合组合推理的反应合成

    本文提出了一种混合表示方法，利用显式和符号表示状态空间，并有效地利用它们的互补优势，从而提供了一种解决 LTLf 到 DFA 转换过程中三个必要条件的技术，从而解决合成中的瓶颈问题。

    Nov, 2019