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

Apr, 2011

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

Dec, 2013

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

Jun, 2024

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

Mar, 2023

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

May, 2007

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

Nov, 2023

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

Aug, 2023

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

Mar, 1999

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

Jul, 2009

本文研究了最小 DFA 的状态复杂度和 infimal prefix-closed 可观察超语言之间的关系，并在此基础上证明了无法用多项式时间算法计算该语言的 DFA，且提出了一种时间复杂度为 O (2^n) 的计算方法。

Mar, 2017