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

Aug, 2023

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

Nov, 2023

本研究发现，当使用好的 MDP Buchi 自动机来代替确定性 Rabin 自动机时，可以更好地将 omega-regular 目标使用于模型无关的强化学习中，并且使用 Streett 自动机所得到的交替好的 MDP 自动机，可以比最小的非确定性 Buchi 自动机更加简洁。

May, 2022

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

Mar, 1999

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

Mar, 2023

本文提出了一个新的模型混合自动机（非确定性 / 概率性），它不仅包括了非确定性自动机，还包括了图形化概率模型，并且它配备了与图形化概率模型继承的并行组合、模拟关系和支持消息传递算法。Segala 的概率自动机可以映射到混合自动机。

Jan, 2022

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

Jun, 2024

针对非确定性概率程序的终止性质，提出了基于多项式守卫和分配的终止分析方法，通过 Positivstellensatz 的方法综合多项式级别超级马丁格斯来证明其终止性，并且还可以合成二次排名超级马丁格斯来处理复杂的程序。

Apr, 2016

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

Oct, 2018

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

Jul, 2009