本文介绍了如何使用改进的 backward 算法处理带有 failure transitions 的 weighted finite-state automata，方法非常高效，同时也给出了特殊情况下的算法复杂度分析。

Jan, 2023

本文提出了一种基于 WFA 状态空间上的半范数的新型仿射（伪）度量，以线性算子集的谱性质为基础，研究了其连续性和应用于加权自动机谱学习的初步结果，并且发现其计算难度为不可判定问题。

Feb, 2017

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

Jul, 2009

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

Aug, 2023

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

May, 2007

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

Nov, 2023

使用 SAT 求解器来寻找有限同步自动机的最短重置词的方法进行描述，并对最短重置词的长度进行了实验研究。根据实验结果，提出一个假设：在具有高概率的 n 个状态和 2 个输入字母的随机有限自动机中，最短重置词的长度相对于 n 是次线性的，并且可以估计为 1.95n 的 0.55 次方。

Apr, 2011

提供了树连接语言、两级形式主义、半环加权版本、字符串求和算法和下推连接自动机的关键算法。

Oct, 2023

研究了 DAG 自动机作为概率模型的可行性，结果表明，通过赋予转换权重，一些单根，多根和无界的 DAG 自动机不能作为有用的概率模型，并且这种问题似乎是普遍存在的，但平面变体不受此影响，但这些变体有其他问题。

Oct, 2018

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

Apr, 2011