2025-11-19T16:52:14.243866

Learning Weighted Automata over Number Rings, Concretely and Categorically

Aristote, van Gool, Petrişan et al.
We develop a generic reduction procedure for active learning problems. Our approach is inspired by a recent polynomial-time reduction of the exact learning problem for weighted automata over integers to that for weighted automata over rationals (Buna-Marginean et al. 2024). Our procedure improves the efficiency of a category-theoretic automata learning algorithm, and poses new questions about the complexity of its implementation when instantiated to concrete categories. As our second main contribution, we address these complexity aspects in the concrete setting of learning weighted automata over number rings, that is, rings of integers in an algebraic number field. Assuming a full representation of a number ring OK, we obtain an exact learning algorithm of OK-weighted automata that runs in polynomial time in the size of the target automaton, the logarithm of the length of the longest counterexample, the degree of the number field, and the logarithm of its discriminant. Our algorithm produces an automaton that has at most one more state than the minimal one, and we prove that doing better requires solving the principal ideal problem, for which the best currently known algorithm is in quantum polynomial time.
academic

Learning Weighted Automata over Number Rings, Concretely and Categorically

基本信息

  • 论文ID: 2504.16596
  • 标题: Learning Weighted Automata over Number Rings, Concretely and Categorically
  • 作者: Quentin Aristote, Sam van Gool, Daniela Petrişan, Mahsa Shirmohammadi
  • 分类: cs.FL (Formal Languages and Automata Theory)
  • 发表时间: 2025年4月23日 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2504.16596

摘要

本文开发了一个通用的主动学习问题归约程序。该方法受到Buna-Marginean等人(2024)最近提出的将整数上加权自动机精确学习问题多项式时间归约到有理数上加权自动机学习问题的启发。该程序提高了范畴论自动机学习算法的效率，并在具体范畴实例化时提出了关于实现复杂性的新问题。作为第二个主要贡献，作者在数环(代数数域中整数环)上加权自动机学习的具体设置中解决了这些复杂性问题。假设数环OK的完整表示，获得了OK-加权自动机的精确学习算法，该算法在目标自动机大小、最长反例长度的对数、数域次数和判别式对数方面具有多项式时间复杂度。算法产生的自动机最多比最小自动机多一个状态，并证明了做得更好需要解决主理想问题，而目前已知的最佳算法是量子多项式时间的。

研究背景与动机

问题背景

  1. 经典自动机学习: Angluin的L*算法在最小充分教师(MAT)框架下高效学习确定性有限状态自动机，这是计算学习理论的经典结果。
  2. 加权自动机学习的挑战: 将学习算法扩展到更表达性的模型(如加权自动机)面临挑战，特别是当权重不在域(field)而在环(ring)中时。
  3. 现有方法局限性:
    • 对于域上的加权自动机，已有多项式时间学习算法
    • 对于一般环上的加权自动机，现有方法要么复杂度过高，要么适用范围有限
    • 范畴论方法虽然通用但在具体实现时可能导致指数复杂度

研究动机

  1. 理论需求: 需要一个既保持范畴论方法通用性又在具体情况下具有多项式复杂度的框架
  2. 实际应用: 数环在密码学等领域有重要应用，对其上加权自动机的高效学习有实际价值
  3. 理论边界: 探索加权自动机最小化的理论极限，特别是Fatou性质的推广

核心贡献

  1. 通用归约算法: 提出了Algorithm 3，这是一个在范畴论框架下的通用归约程序，将一类学习问题归约到另一类更易处理的学习问题
  2. 数环上的具体算法: 开发了Algorithm 4，专门针对数环OK上加权自动机的多项式时间学习算法
  3. 几乎最优性结果: 证明了算法产生的自动机最多比最小自动机多一个状态(几乎最小性)
  4. 理论复杂度边界: 证明了获得完全最小的自动机等价于解决主理想问题(PIP-hard)，建立了问题的理论下界
  5. Fatou性质推广: 证明了Dedekind域是"几乎强Fatou环"，推广了经典的Fatou性质

方法详解

任务定义

输入: 一个未知的OK-加权语言L: Σ* → OK (通过oracle访问) 输出: 一个计算L的OK-加权自动机 约束: 算法复杂度为目标自动机大小、最长反例长度对数、数域次数和判别式对数的多项式

核心技术框架

1. 范畴论基础

论文采用函子视角，将自动机视为函子A: I → C，其中：

  • I是由字母表Σ生成的自由范畴
  • C是输出范畴(如模范畴ModR)

2. 通用归约算法(Algorithm 3)

算法思想：
1. 在"易处理"范畴D中学习自动机
2. 通过函子F: C → D建立联系
3. 使用右伴随G: D → C将结果拉回到目标范畴C

关键假设(Assumption 12):

  • F保持某些态射类
  • F有右伴随G
  • 单位和余单位态射具有特定性质

3. 数环上的具体实现(Algorithm 4)

步骤1: 后向共轭

计算自动机A的后向空间的基B
通过矩阵B共轭A得到A'

步骤2: 前向模生成

调用Algorithm 5计算A'的前向OK-模的生成集
使用两阶段策略：
- 第一阶段：在K中找到增加秩的词
- 第二阶段：在OK中完成模的生成

步骤3: 伪基计算

使用伪Hermite标准形(pseudo-HNF)从生成集计算伪基
伪基形式：{(ai, vi) | 1 ≤ i ≤ ℓ}，其中ai是分式理想

步骤4: 几乎最小生成集

通过Algorithm 6将伪基转换为大小至多ℓ+1的生成集
使用理想因子精化和中国剩余定理

技术创新点

  1. 两阶段生成策略: 先在域K中确定秩，再在环OK中完成模结构，避免了指数复杂度
  2. 伪基技术: 利用Dedekind域的结构理论，通过伪基处理非主理想域的情况
  3. 范畴论与具体算法的结合: 将抽象的范畴论框架具体化为可实现的多项式算法

实验设置

理论验证

论文主要是理论工作，通过以下方式验证：

  1. 复杂度分析: 详细分析了Algorithm 4和Algorithm 5的时间复杂度
  2. 正确性证明: 通过Theorem 18证明了通用算法的正确性
  3. 实例验证: 提供了具体例子(如Example 1)说明Zi√5上的情况

复杂度界限

定理2: 给定OK的完整表示，OK-加权自动机的精确学习在以下参数的多项式时间内可解：

  • 目标自动机大小
  • 最长反例长度的对数
  • 数域次数d
  • 判别式ΔK的对数

实验结果

主要理论结果

  1. 几乎最优性(Proposition 10): 对于Dedekind域R，如果L是秩为n的R-加权语言，则存在至多n+1个状态的R-加权自动机计算L
  2. 复杂度下界(Proposition 26): 判断OK-加权自动机是否状态最小是PIP-困难的
  3. Fatou性质推广(Corollary 16): Dedekind域是几乎强Fatou环

具体实例分析

Example 1: 在数环R = Zi√5中：

  • 构造了一个3状态的R-加权自动机
  • 存在等价的2状态K-加权自动机(K = Q(i√5))
  • 说明了强Fatou性质不总是成立，但几乎强Fatou性质成立

相关工作

经典自动机学习

  • Angluin的L*算法：确定性有限自动机的多项式学习
  • Beimel等人：域上加权自动机的学习算法

环上加权自动机

  • van Heerdt等人：主理想域上的学习，但无复杂度界限
  • Buna-Marginean等人：Z到Q的归约，本文的直接启发

范畴论方法

  • Colcombet-Petrişan：自动机最小化的函子方法
  • Urbat-Schröder等人：学习的代数方法

结论与讨论

主要结论

  1. 开发了数环上加权自动机学习的首个多项式时间算法
  2. 证明了获得完全最小自动机的困难性(PIP-hard)
  3. 建立了范畴论与具体算法之间的桥梁

局限性

  1. 表示要求: 需要数环OK的"完整表示"，这可能在实践中难以获得
  2. 几乎最优性: 算法产生的自动机可能比最小的多一个状态
  3. 特定结构: 方法专门针对Dedekind域，对一般环的推广不明确

未来方向

  1. 其他环类: 研究在非Dedekind域上的推广
  2. 实际实现: 开发具体的软件实现和实验验证
  3. 应用探索: 在密码学等领域的具体应用

深度评价

优点

  1. 理论深度: 巧妙结合了范畴论、代数数论和计算复杂性理论
  2. 技术创新: 两阶段学习策略和伪基技术的使用很有创意
  3. 完整性: 既给出了算法又证明了下界，提供了问题的完整图景
  4. 严谨性: 数学证明严谨，复杂度分析详细

不足

  1. 实用性: 缺乏实际实现和实验验证
  2. 可读性: 对于非专家来说，范畴论部分可能较难理解
  3. 适用范围: 方法的适用性受限于特定的代数结构

影响力

  1. 理论贡献: 为加权自动机学习理论做出了重要贡献
  2. 方法论: 展示了如何将抽象的范畴论方法具体化
  3. 跨领域: 连接了自动机理论、代数数论和计算复杂性

适用场景

  1. 密码学: 数环在格密码学中的应用
  2. 符号计算: 代数数域上的计算问题
  3. 理论研究: 为进一步的自动机学习研究提供基础

技术细节补充

数环的表示

论文要求OK的"完整表示"包括：

  • 积分基Ω = {ω1,...,ωd}
  • 本原元素θ及其最小多项式
  • 复杂度度量CK = d⁴(log d + log ΔK)

算法复杂度

关键的复杂度界限来自：

  • 伪HNF计算：多项式时间(Biasse-Fieker-Hofmann)
  • 严格递增链长度：由Lemma 24界定为log(N(d))
  • 理想操作：在CK中多项式时间

这篇论文在理论计算机科学领域做出了重要贡献，特别是在自动机学习和代数计算的交叉领域。虽然实用性有待验证，但其理论价值和方法论意义是显著的。