AAAINov, 2022

自动机级联：表达能力与样本复杂度

PDF
TL;DR基于 Prime Decomposition 定理，本文介绍自动机级联作为自动机复杂系统的一种结构化和模块化方式；并且证明了样本复杂度可以通过组件数量和单个组件的最大复杂度来描述，由此学习表示多组分相互作用的大型动态系统的自动机的数量可以呈指数级增长。
发现论文，激发创造
  • Krohn-Rhodes 逻辑

    本论文提出了一种新的过去式模态时态逻辑家族，通过扩展 Past LTL 变得更加丰富，以 Krohn and Rhodes 关于自动机串联理论为基础，并展示了该家族被称为 Krohn-Rhodes Logics 的无穷多个扩展，可以捕捉到更多的基础自动机和扩展其表达能力。

    Apr, 2023

  • 基于数据驱动的混合自动机框架用于建模复杂动态系统

    提出一个计算高效的数据驱动式混合自动机建模方法，基于多个神经网络来捕捉未知复杂系统的行为，并且采用区间分析和分裂合并过程来提供集值可达性分析，以减少可达集计算的计算成本同时不影响建模精度。

    Apr, 2023

  • 输出分解学习 Mealy 机器

    我们提出了一种主动自动机学习算法，它基于将个别输出进行投影从而学习一个有限状态机的分解。这与 Labbaf 等人 (2023) 提出的最近的组合学习算法互为对偶。当将输出投影到一个较小的集合时，模型本身也会缩小。通过有几个这样的投影，我们不会丢失任何信息，完整的系统可以被重建。根据系统的结构，这大大减少了查询的数量，如算法的初步评估所示。

    May, 2024

  • 学习产品自动机

    本文介绍适用于学习 Moore 机的主动学习算法的优化方法，其中输出包括多个可观测量，并通过投影分解为较小的组件进行学习，这对于学习软件尤为重要，因为组合方法对于保证可扩展性非常重要。

    May, 2017

  • 神经自动机的不变量

    本文介绍了一种神经动力学系统的符号计算表示理论，旨在研究不同编码下神经自动机的对称性和不变性质，结果表明只有针对等式模式的阶跃函数在重新编码后是不变的，而平均激活水平是不变的。

    Feb, 2023

  • 语言模型级联

    通过利用概率编程技术以及组合多个模型，并在测试中反复交互，我们提出了一种基于语言模型层级结构的模型组合方法，以实现对复杂数据类型（如字符串）的快速学习和推理。

    Jul, 2022

  • 用理论模态行动语言表示混合自动机

    该研究论文介绍了混合自动机和行为语言之间的形式关系，并展示了如何用 action language 表示混合自动机，然后介绍了一个用混合自动机模型研究系统并利用 dReal 求解的原型系统。

    Jul, 2017

  • 从长执行跟踪中学习简洁模型

    通过自动提取硬件 / 软件系统执行轨迹中的自动机模型和轨迹分割来综合捕捉事务级、系统范围的行为模式，并实验验证了该方法的有效性。

    Jan, 2020

  • 动态输入 / 输出自动机：动态系统的正式且组合模型

    提出了一种动态 I/O 自动机（DIOA）的组件化模型，具有操作符，可以动态创建和销毁自动机，并可以动态更改其签名，它可以模拟移动性，是层次化的，并可以使用跟踪包容性进行行为子类型化。同时，该模型具备并行组合，操作隐藏，操作重命名的操作符。

    Apr, 2016

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

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

    Aug, 2023