2025-11-25T19:49:18.778457

Active Learning of Deterministic Transducers with Outputs in Arbitrary Monoids

Aristote

We study monoidal transducers, transition systems arising as deterministic automata whose transitions also produce outputs in an arbitrary monoid, for instance allowing outputs to commute or to cancel out. We use the categorical framework for minimization and learning of Colcombet, PetriÅan and Stabile to recover the notion of minimal transducer recognizing a language, and give necessary and sufficient conditions on the output monoid for this minimal transducer to exist and be unique (up to isomorphism). The categorical framework then provides an abstract algorithm for learning it using membership and equivalence queries, and we discuss practical aspects of this algorithm's implementation.

academic

Active Learning of Deterministic Transducers with Outputs in Arbitrary Monoids

基本信息

论文ID: 2410.01590
标题: Active Learning of Deterministic Transducers with Outputs in Arbitrary Monoids
作者: Quentin Aristote (Université Paris Cité, CNRS, Inria, IRIF)
分类: cs.FL (Formal Languages and Automata Theory)
发表时间/会议: Logical Methods in Computer Science, Volume 21, Issue 4, 2025 (已被接收，2024年10月提交)
论文链接: https://arxiv.org/abs/2410.01590

摘要

本文研究单子转换器(monoidal transducers)，这是一类确定性自动机的转换系统，其转换过程会在任意单子中产生输出，例如允许输出交换或相互抵消。作者使用Colcombet, Petrişan和Stabile的分类框架来恢复识别语言的最小转换器概念，并给出输出单子上的必要充分条件，使得这种最小转换器存在且唯一(同构意义下)。该分类框架进而提供了使用成员查询和等价查询来学习最小转换器的抽象算法，并讨论了该算法实现的实际方面。

研究背景与动机

问题定义

传统的转换器(transducers)通常在自由单子(如字符串)上产生输出，但在某些应用场景中，输出可能需要满足交换律或抵消律等代数性质。例如：

并发理论中的trace单子：用于建模独立作业的执行序列，某些作业可以异步运行
程序调度：转换器可用于程序化地调度作业
自然语言处理：某些输出符号可能具有交换性质

研究动机

现有的转换器学习算法(如Vilar算法)主要针对自由单子设计，直接应用于非自由单子会遇到以下问题：

非终止性：如Lemma 1.1所示，在某些单子上Vilar算法可能永不终止
效率问题：先学习自由单子上的转换器再最小化的方法会引入不必要的状态
理论缺失：缺乏针对任意单子的系统性理论框架

现有方法局限性

Gerdjikov的工作提供了最小化条件但未涉及学习问题
现有学习算法假设输出在自由单子中
缺乏统一的理论框架处理任意单子

核心贡献

理论框架扩展：将Colcombet-Petrişan-Stabile的分类学习框架扩展到单子转换器
存在性条件：给出输出单子的必要充分条件，确保最小单子转换器存在且唯一
条件优化：扩展了Gerdjikov的最小化条件类别，虽然复杂度界限可能更差
实用算法：提供抽象单子转换器学习算法的具体实现细节
分解系统：通过四元分解系统解释学习算法中不同类型的一致性问题

方法详解

任务定义

输入：

输入字母表A (可数)
输出单子M = (M, ε, ⊗)
目标函数L: A* → M + 1 (部分函数)

输出：识别L的最小单子转换器

查询类型：

成员查询EvalL：给定输入词w，返回L(w)
等价查询EquivL：给定假设转换器，判断是否正确或返回反例

理论基础

单子转换器建模

单子转换器被建模为函子A: I → Kl(TM)，其中：

I是输入范畴，表示转换器的基本结构
Kl(TM)是单子TM的Kleisli范畴
TM X = M × X + 1 = (M × X) ⊔ {⊥}

关键数学结构

左最大公因数(left-gcd)：对于族w = (wi)i∈I，其左gcd是被所有其他左因数整除的左因数。

约化函数：当Kl(TM)具有所有可数1的幂时，存在函数：

lgcd: (M + 1)^N* → M (计算左gcd)
red: (M + 1)^N* → (M + 1)^N* (约化函数)

满足条件：

Λ = lgcd(Λ) ⊗ red(Λ)
唯一性：若υ ⊗ red(Γ) = ν ⊗ red(Λ)，则υ = ν且red(Γ) = red(Λ)

存在性条件

定理：Kl(TM)具有所有可数1的幂当且仅当M满足：

左可约性：左可约到左可逆元
右互质可约性：对左互质族的右互质可约性
唯一左gcd：所有非空可数族具有唯一的左gcd(右可逆意义下)

分解系统

论文定义了三个分解系统：

(E₁,M₁) = (Surj ∩ Inj ∩ Inv, Tot)
(E₂,M₂) = (Surj ∩ Inj, Inv ∩ Tot)
(E₃,M₃) = (Surj, Inj ∩ Inv ∩ Tot)

主要使用(E₃,M₃)定义最小转换器，它推广了自由单子情况下的分解系统。

学习算法

算法框架(Algorithm 2)

输入: EvalL, EquivL
输出: 最小转换器MinL

1. 初始化Q = T = {ε}
2. 循环直到收敛:
   - 检查闭包条件：是否存在qa ∈ QA使得R(q,a,·)不能表示为已有状态的可逆倍数
   - 检查一致性条件：检查三种一致性问题
   - 构建假设转换器H(Q,T)
   - 提交等价查询，处理反例