九 章 格 数 学 · 数 学 前 沿 · V I P 专 阅

极端自动机的分类

《半群中的 50 个公开问题》 · 问题 28 专题综述

题面达到同步化长度上界的自动机(Černý 自动机及「准 Černý」族)之外,极端族的完全分类是什么?

本页为 VIP 专阅综述:主要概念的详细介绍与主要命题的细致证明,全文见下方专阅区。

问题

若 Černý 猜想(21 号)真, «达到 (n−1)² 的自动机»(极端自动机)是 «等号族»——它们的完全分类是猜想的 «精化»。已知达到或接近上界的族:Černý 自动机(精确达到)、Kari 自动机(n²−3n+3 型,接近)、Roman 自动机( «几乎二重» 型)、Ananichev–Volkov 的 «慢» 变体族。 «这些就是全部吗» 的枚举式分类未完成——它与 21 号互为表里(分类的任何推进都约束猜想的反例空间)。

主要概念

«慢» 自动机与 «压缩结构»

极端自动机的共同结构特征: «压缩能力极度稀薄»——每步只压缩 «特定配置» 的状态集, «无压缩段» 长( «慢» 的来源)。Černý 自动机的 «单压缩点»(b 只压 0)、Kari 自动机的 «两段式压缩»、Roman 的 «二重结构»—— «慢» 的 «机制分类» 是分类问题的对象。 «准 Černý»( «慢» 但不达 (n−1)²)的 «距离上界的差» 如何量化,是分类的定量面。

枚举与 «反例空间»

计算机枚举(小 n 的全部同步自动机穷举)给出 «极端族» 在 n ≤ 7 左右的完整表—— «已知的慢族覆盖了表中全部极端例»; «n 增大后出现新族» 的可能性是分类的核心未知。分类的 «代数面»:极端自动机的 «转移半群» 有什么不变量( «压缩能力的 «谱»»)—— «谱» 的刻画等价于 «界的精化»。

主要命题与证明

命题 1(Černý 族在极小 n 的唯一性;陈述与枚举口径) 计算机穷举:对 n ≤ 6(文献口径的精确范围),达到最坏同步长度的自动机(在 «二元字母表» 类内)都是 Černý 自动机的同构变体—— «极端 = Černý» 在小 n 成立; «n ≥ 7 的新族»(如 Kari 的 n=7? 例)打破唯一性, «分类» 随之复杂化。

现状说明 穷举的范围与 «字母表大小» 的限制(穷举多限于二元字母表)是 «枚举分类» 的双重天花板; «极端族的 «代数签名»»(转移半群的不变量)若找到,穷举可被 «签名匹配» 替代——这是分类问题的 «算法化路线»。□

命题 2(Kari 与 Roman 族的 «慢» 结构;陈述) Kari 自动机(2003 发现)达同步长 n²−3n+3(与 (n−1)² 差 n−4);Roman 自动机 «二重» 结构达 (n−1)² 型的次级上界。两族的 «压缩谱» 与 Černý 不同( «双点压缩» vs «单点压缩»),说明 «极端» 不是单一机制——分类须按 «压缩机制» 分型。

现状说明  «压缩机制» 的分型( «单点»、 «多点»、 «二重»)已有词汇但没有定理级的 «完备分型»; «机制 × 界常数» 的联合谱( «每型达到的界»)是 21 号猜想的 «分型精化»——若每型的界都 ≤ (n−1)² 且 «型完备»,猜想随分类解决。□

命题 3( «距离上界» 的定量谱;陈述)  «慢» 族达到的长度与 (n−1)² 的 «差» 的可能值谱:已知差 0(Černý)、n−4(Kari)等; «可能差值» 的完全谱( «差能否为 1?2?»)、 «慢族的 «闭包»»(组合、幂化是否仍慢)都开放。它与 27 号(部分自动机)的 «慢» 机制对照:完全自动机的 «慢» 被二次界 «封顶»,部分自动机的 «慢» 无顶。

现状说明  «差值谱» 的研究工具是 «极值枚举» 与 «机制反演»( «给定差值,构造达到者»)—— «反演» 的可行范围逐 n 扩大但无一般定理。□

进展与文献

Černý(1964);Kari 的慢自动机(2003);Roman(Ananichev–Volkov 的系列研究);Ananichev–Volkov «Slowly synchronizing automata» 系列;Gusev–Maslennikova 的穷举。开放核心:极端族的完备分型; «压缩谱» 的定理化; «慢» 与猜想的联合解决路线。

← 返回问题 28