Apr, 2011

随机自动机的最短重置词的实验研究

PDF
TL;DR使用 SAT 求解器来寻找有限同步自动机的最短重置词的方法进行描述，并对最短重置词的长度进行了实验研究。根据实验结果，提出一个假设：在具有高概率的 n 个状态和 2 个输入字母的随机有限自动机中，最短重置词的长度相对于 n 是次线性的，并且可以估计为 1.95n 的 0.55 次方。
finite synchronizing automatonsat solvershortest reset wordexperimental studysublinear
发现论文，激发创造
  • 修改最小同步词长度上限

    研究确定性有限自动机中的同步（周期，重置，幻数，可定向）字，并将上限值从（n^3-n）/6 降至 n（7n^2+6n-16）/48，同时提出了一种用于找到带有限制上界的同步字的算法。

    Apr, 2011

  • 使用 Answer Set Programming 生成最短同步序列

    检查有限自动机同步序列是否存在和找到最短同步序列是多项式时间内可解的，但是找到最短同步序列问题被称为 NP-hard 问题。本文研究了与暴力算法和基于 SAT 的方法相比，应用 Answer Set Programming 解决该优化问题的有效性。

    Dec, 2013

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

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

    Mar, 2023

  • 正则语言等价性检查

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

    Jul, 2009

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

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

    Jun, 2024

  • 实时正则表达式匹配

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

    Aug, 2023

  • 一维量子有限自动机：优点、缺点和推广

    研究了 1 - 方式量子有限自动机的表现并与它们的经典对应物进行了比较，发现随着正确率降低，量子自动机比可逆自动机更有优势；构建了一个比任何等效的经典（甚至随机化的）有限自动机指数级更小的 1 - 方式 QFA，这个构造可能对设计其他空间高效量子算法有用；探讨了 1 - 方式 QFA 的几个推广模型，以找到一个保持量子部分尽可能简单且比 1 - 方式 QFA 更强大的模型。

    Feb, 1998

  • 从不确定性 Büchi 和 Streett 自动机到确定性 Parity 自动机

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

    May, 2007

  • 非幂等半环中的 A* 最短字符串解码

    该论文提出了一种基于 Astar 搜索的算法，使用确定性自动机的后向最短距离作为启发式来找到非确定性有权自动机上的最短字符串，从而解决了在非幂等半环中单一最短路径算法未定义的问题。

    Apr, 2022

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

    我们使用转移半群建立一种有限状态自动机的即时确定化的抽象，并展示了如何应用它来界定渐近性。我们呈现了足够导致确定自动机的多项式状态复杂性的代数和组合特性。我们发现的一个特例是，具有许多非确定性转换的自动机几乎总是适用于多项式复杂性的确定化。此外，我们将我们的思想扩展到加权有限状态自动机。

    Aug, 2023